二分答案while什么时候<=,什么时候<?
查看原帖
二分答案while什么时候<=,什么时候<?
463562
Dreamerlee✅楼主2021/2/28 11:20

这个二分答案的写成这样就只能90分

while(lef < rig)
    {
        mid = lef+((rig-lef) >> 1);
        if(judge(mid))
        {
            ans = mid;
            lef = mid +1;
        }
        else
            rig = mid;
    }

写成这样就可以100分,为什么??

while(lef <= rig)
    {
        mid = lef+((rig-lef) >> 1);
        if(judge(mid))
        {
            ans = mid;
            lef = mid + 1;
        }
        else
            rig = mid - 1;
    }

/***********************分割线,完整90分代码/

#include <iostream>
#include <cstdio>
using namespace std;
long long l, n, m,d[50010],lef,rig,mid, ans;
inline long long read()
{
    long long x=0,f=1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-')
            f=-1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x=(x<<1)+(x<<3)+ ch - '0';
        ch = getchar();
    }
    return x*f;
}
bool judge(int x)
{
    int j = 0, now = 0, sum=0;
    while(j < n+1)
    {
        ++j;
        if(d[j] - d[now] < x)
            ++sum;
        else
            now = j;
    }
    if(sum <= m)
        return true;
    else
        return false;
}
int main()
{
    l = read(),n = read(), m = read();
    for(int i = 1; i <= n; i++)
        d[i] = read();
        d[n+1] = l;
    lef=1,rig=d[n+1];
    while(lef < rig)
    {
        mid = lef+((rig-lef) >> 1);
        if(judge(mid))
        {
            ans = mid;
            lef = mid +1;
        }
        else
            rig = mid;
    }
    cout << ans;
    return 0;
}

2021/2/28 11:20
加载中...