poj 3258 River Hopscotch(二分+贪心)

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

题意:

一条河长度为 L,河的起点(Start)和终点(End)分别有2块石头,S到E的距离就是L。

河中有n块石头,每块石头到S都有唯一的距离

问现在要移除m块石头(S和E除外),每次移除的是与当前最短距离相关联的石头,

要求移除m块石头后,使得那时的最短距离尽可能大,输出那个最短距离。

和3273差不多。。。

 #include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int maxn = +;
int a[maxn]; int main()
{
int l, n, m, i;
int low, mid, high, sum, cnt;
cin>>l>>n>>m;
a[n+] = l;
low = l;
high = l;
for(i = ; i <= n; i++)
{
cin>>a[i];
}
sort(a+, a+n+);
for(i = ; i <= n+; i++)
if(a[i]-a[i-]<low)
low = a[i]-a[i-]; while(high>=low) //注意‘=’号
{
sum = ; cnt = ;
mid = (high+low)/;
for(i = ; i <= n+; i++)
{
sum += a[i]-a[i-];
if(sum<mid)
cnt++;
else
sum = ;
}
if(cnt<=m) //注意‘=’号
low = mid+;
else
high = mid-;
}
cout<<high<<endl;
return ;
}

以后还是用这种形式的二分吧

while(left<right)

{

if()

left=mid+1;

else right=mid;

}

代码:

 #include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int maxn = +;
int a[maxn]; int main()
{
int l, n, m, i, f;
int low, mid, high, sum, cnt;
cin>>l>>n>>m;
a[n+] = l;
low = l;
high = l;
for(i = ; i <= n; i++)
{
cin>>a[i];
}
sort(a+, a+n+);
for(i = ; i <= n; i++)
if(a[i]-a[i-]<low)
low = a[i]-a[i-]; f = ;
while(high>low)
{
sum = ; cnt = ;
mid = (high+low)/;
for(i = ; i <= n; i++)
{
sum += a[i]-a[i-];
if(sum<mid)
cnt++;
else
sum = ;
}
if(cnt > m)
{
high = mid;
f = ;
}
else
low = mid+;
//cout<<low<<endl<<high<<endl;
}
if(f)
cout<<high-<<endl;
else
cout<<high<<endl;
return ;
}

还有http://blog.csdn.net/jackyguo1992/article/details/8665202

这篇博客以这两道题为例, 说明了二分时的易错的情况

上一篇:Sql Server函数全解(二)数学函数


下一篇:linux系统下,11款常见远程桌面控制软件