求助大佬QAQ萌新翻车了
查看原帖
求助大佬QAQ萌新翻车了
1261713
vvwvv楼主2025/2/8 00:50

代码如下,一个测试点也没过,实在看不出来哪错了QAQ。

#include<bits/stdc++.h>
using namespace std;
using ll = long long ;
ll l,n,k;
ll arr[100000+10];//存每个路标的位置

bool judge(ll x)//函数用于判断 以x作为空旷指数 是否可行
{
    ll cnt = 0;//用于统计放入路标个数

    for(int i=1; i<=n+1; i++)//判断每个区间是否需要放入路标,若需要,则计算路标个数
    {
        if(arr[i]-arr[i-1]<=x)continue;//不用放路标
        else//需要放路标,计算 放入的路标个数
        {
            for(int j=2; j<=k+1; j++)//把j当除数,j-1就是放入i与i-1区间的路标个数
            {
                if((arr[i]-arr[i-1])%j==0 && (arr[i]-arr[i-1])/j<=x)
                {
                    cnt+=j-1;
                    break;
                }
                else if((arr[i]-arr[i-1])%j!=0 && (arr[i]-arr[i-1])/j +1<=x )
                {
                    cnt+=j-1;
                    break;
                }
            }
        }
    }
    if(cnt==k)return 1;
    return 0;
}

int main()
{
    cin>>l>>n>>k;
    arr[0]=0;//起点坐标初始化
    arr[n+1]=l;//终点坐标初始化
    for(int i=1; i<=n; i++)//读入数据
        scanf("%lld",&arr[i]);

    //二分答案
    ll left = 0 , right = l;
    while(left<=right)
    {
        ll mid = (left + right)/2;
        if(judge(mid))
            right = mid - 1;
        else
            left = mid + 1;
    }
    cout<<right+1;
    return 0;
}

2025/2/8 00:50
加载中...