POJ 3258 River Hopscotch 二分枚举

题目:http://poj.org/problem?id=3258

又A一道,睡觉去了。。

 #include <stdio.h>
#include <algorithm> int d[];
int s, n, m; bool judge(int mid)
{
int sum = , cnt = ;
for(int i = ; i <= n+; i++)
{
sum += d[i] - d[i-];
if(sum < mid)
cnt++;
else
sum = ;
}
if(cnt > m)
return ;
else return ;
} int main()
{
scanf("%d %d %d", &s, &n, &m);
for(int i = ; i <= n; i++)
{
scanf("%d", &d[i]);
}
d[] = ;
d[n+] = s;
std::sort(d, d+n+); int low = , high = s+, mid;
while(low < high)
{
mid = (high + low) / ;
if(judge(mid))
high = mid;
else
low = mid + ;
}
printf("%d\n", low-);
return ;
}
上一篇:GIt 从入门到放弃


下一篇:从零开始学Sketch——进阶篇-b