POJ3258 River Hopscotch

Posted on | In |

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

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

问现在要移除m块石头（S和E除外），每次移除的是与当前最短距离相关联的石头，要求移除m块石头后，使得那时的最短距离尽可能大，输出那个最短距离。

思路

对于每个给定的距离dis 摘掉与其大于dis的石块 看摘掉的石块数量<=m

典型的最大化最小值题

贪心二分的思想

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<iostream> 
#include <cstring>
#include <algorithm> 
#define ll long long
using namespace std;
ll m,n,d;
int a[100000];
//函式明顯有單調性，相鄰石頭間的最短距離 d 越小越容易達成。
bool check(int mid){
	ll cnt=0;
	int pre=0;/// 前一個石頭是誰，初使值為起點 rocks[0]
	for(int i=1;i<n+2;i++){
		if(a[i]-a[pre]<mid) cnt++;
		else pre=i;//!!!不能写pre++ 
	}
	if(cnt>m) return false;
	else return true;
}
int main(){
	scanf("%d%d%d",&d,&n,&m);
		a[0]=0;
	for(int i=1;i<n+1;i++){//!!!
		scanf("%d",&a[i]);
	}

	a[n+1]=d;

	sort(a,a+n+2);
// for(int i=0;i<n+2;i++)
//	cout<<a[i]<<" ";
	int L,R,ans=0;
	L=0;
	R=d;
	while(L<=R){
		int mid=(L+R)/2;
		if(check(mid)){
			ans=mid;
			L=mid+1;
		}
		else R=mid-1;
	}
	cout<<ans<<endl;	
	return 0;
}

可参考

http://www.hankcs.com/program/cpp/poj-3258-river-hopscotch.html

https://amoshyc.github.io/ojsolution-build/poj/p3258.html