# POJ 3258 River Hopscotch （二分）

```#include <iostream>
#include <string.h>
#include <math.h>
#include <queue>
#include <algorithm>
#include <stdlib.h>
#include <map>
#include <set>
#include <stdio.h>
using namespace std;
#define LL __int64
#define pi acos(-1.0)
const int mod=9901;
const int INF=0x3f3f3f3f;
const double eqs=1e-8;
int a[51000], vis[51000];
int bin_search(int n, int m)
{
int low=0, high=1e9, mid, ans, cnt, last;
while(low<=high) {
mid=low+high>>1;
int flag=0;
cnt=0;
last=0;
memset(vis,0,sizeof(vis));
for(int i=0; i<n; i++) {
if(a[i]-last<mid) {
cnt++;
if(cnt>m)
break;
} else {
last=a[i];
vis[i]=1;
}
}
for(int i=n-1;i>=0;i--){
if(vis[i]){
if(a[n]-vis[i]<mid){
cnt++;
if(cnt>m) break;
}
else break;
}
}
if(cnt>m) high=mid-1;
else{
ans=mid;
low=mid+1;
}
}
return ans;
}
int main()
{
int lenth, i, n, m, ans;
scanf("%d%d%d",&lenth,&n,&m);
for(i=0; i<n; i++) {
scanf("%d",&a[i]);
}
if(!n) {
printf("%d\n",lenth);
return 0;
}
sort(a,a+n);
a[n]=lenth;
ans=bin_search(n,m);
printf("%d\n",ans);
return 0;
}
```

POJ 3258 River Hopscotch （二分）

• 0

开心

• 0

板砖

• 0

感动

• 0

有用

• 0

疑问

• 0

难过

• 0

无聊

• 0

震惊

1143: [CTSC2008]祭祀river Time Limit: 10 Sec Memory Limit: 162 MB Submit: 2026 Solved: 1017 [
K Best Time Limit: 8000MS Memory Limit: 65536K Total Submissions: 6419 Accepted: 1712 Case Ti
Garland Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 1184 Accepted: 515 Descrip

Garland Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 1438 Accepted: 638 Descrip
Squares Time Limit: 3500MS Memory Limit: 65536K Total Submissions: 17554 Accepted: 6678 Descr
Description My birthday is coming up and traditionally I'm serving pie. Not just one pie, no,
Pie Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 14107 Accepted: 4837 Special J