一道二分答案题,判断时只需将距离遍历一遍,即可统计出需要移走多少块石头
#include<cstdio> using namespace std; int a[50005], n, m, t; bool judge(int x) { int s = 0, now = 0; for(int i = 1; i <= n; i++) { if(a[i] - a[now] < x) s++; else now = i; } return s <= m; } int main() { int l = 0, r = 10000000, mid; scanf("%d %d %d", &t, &n, &m); for(int i = 1; i <= n; i++) scanf("%d", &a[i]); while(l <= r) { mid = (l + r) >> 1; if(!mid)//l=0, r=0会死循环 break; if(judge(mid)) l = mid + 1; else r = mid - 1; } if(n == 0 || m == 0) r = t; printf("%d", r); return 0; }