P2678 跳石头

一道二分答案题,判断时只需将距离遍历一遍,即可统计出需要移走多少块石头

#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;
} 

 

上一篇:洛谷P2678跳石头 二分答案


下一篇:洛谷 p2678 跳石头 题解