60求助,2,3,4,7WA
查看原帖
60求助,2,3,4,7WA
56749
default111楼主2020/10/20 11:22

solve函数二分,judge函数判断,不知道哪里有问题,求助。

#include<cstdio>
#define N 50005
int a[N];
int l,n,m;
bool judge(int x)
{
    int tot=0,i=0,now=0;
    /*
    for(int i=0;i<=n;i++)
    {
        if(dis[i]<x) {
            dis[i+1]+=dis[i];
            ans++;
        }
        if(ans>m) return false;
    }
    */

    while(i<n+1) {
        i++;
        if((a[i]-a[now])<x) {
            tot++;
        }
        else now=i;
        if(tot>m) return false;
    }
    return true;
}
void solve()
{
    int lb=1,rb=l+1;
    while((rb-lb)>1)
    {
        int mid=(rb+lb)>>1;
        if(judge(mid)) lb=mid;
        else rb=mid;
    }
    printf("%d",lb);
}
int main()
{
    scanf("%d%d%d",&l,&n,&m);
    a[n]=l;
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
    solve();
    return 0;
}
2020/10/20 11:22
加载中...