A-排船的问题
很显然，这个数据范围用二分来找这个最长的最短是OK的，
然后我们就判断一下二分到的东西，用一个贪心，就是尽可能将每一个往左边放，但不能与船重叠，也不能超过我们二分到的最长的绳的长度，因为要尽可能给后面留出空间，让后面的绳的长度不超过我们二分到的长度。
然后如果最后极限的方法仍飞出了港口，那自然就是不行的，就继续二分。
可以这样理解。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e4+5;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(!isdigit(ch))
{
if(ch=='-') f=-1;
ch=getchar();
}
while(isdigit(ch))
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
int n,x,m;
int p[MAXN];
inline bool check(int pos)
{
int head=0,tail=0;
for(int i=1;i<=n;i++)
{
head=tail;
if(head+x>p[i]+pos) return false;
tail=max(head+2*x,p[i]-pos+x);
}
if(tail>m) return false;
return true;
}
int main()
{
n=read(),x=read(),m=read();
for(int i=1;i<=n;i++) p[i]=read();
if((x*2*n)>m) {printf("-1\n");return 0;}
int l=0,r=m-1,ans;
while(l<=r)
{
int mid=(l+r)>>1;
if(check(mid))ans=mid,r=mid-1;
else l=mid+1;
}
printf("%d\n",ans);
return 0;
}
B-稳定桌
点击查看代码