本文共 1297 字，大约阅读时间需要 4 分钟。
二分跳跃的最短距离 mid 。暴力判断如果有两个石头直接的距离小于 mid ，就把这个石头拿走。如果拿走的石头数目 cnt ≤ m，说明二分的答案可行，ans = mid，接着二分更短的跳跃距离。
#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define lck_max(a,b) ((a)>(b)?(a):(b))#define lck_min(a,b) ((a)<(b)?(a):(b))typedef long long LL;const int maxn=5e5+7;LL d,n,m;LL t[maxn];inline LL read(){ LL kr=1,xs=0; char ls; ls=getchar(); while(!isdigit(ls)) { if(!(ls^45)) kr=-1; ls=getchar(); } while(isdigit(ls)) { xs=(xs<<1)+(xs<<3)+(ls^48); ls=getchar(); } return xs*kr;}inline void out(LL xs){ if(!xs) {putchar(48); return;} if(xs<0) putchar('-'),xs=-xs; int kr[57],ls=0; while(xs) kr[++ls]=xs%10,xs/=10; while(ls) putchar(kr[ls]+48),ls--;}LL cnt,i,now;inline bool check(LL u){ cnt=0,i=0,now=0; while(i<=n) { i++; if(t[i]-t[now] m) return false; else return true;}LL ans;inline void query(LL l,LL r){ while(l<=r) { LL mid=l+r>>1; if(check(mid)) ans=mid,l=mid+1; else r=mid-1; }}int main(){ d=read();n=read();m=read(); for(LL i=1;i<=n;i++) t[i]=read(); t[n+1]=d;//终点到起点的距离。 query(1,d); out(ans),putchar('\n');return 0;}
转载于:https://www.cnblogs.com/lck-lck/p/9856518.html