这个二分答案的写成这样就只能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;
}