复习一下二分答案

蓝桥杯省赛前的专题复习
先贴上一个关于小数的模板，容易错~！

const double eps=1e-6;
double l,r,mid;
while(r-l>eps){
	mid=(left+right)/2;
	if(check(mid)){
		l=mid;
	}else{
		r=mid;
	}
}
return mid;

一个经典的关于距离的二分答案问题（POJ2456）：

在中国传媒大学的钢琴湖里有C只天鹅，XH0822为它们建造了一座包括N个隔间的天鹅棚，分别在坐标轴上的x1，…，xN位置。但这些天鹅都彼此看不惯对方，为了防止他们互相伤害，所以不能把几只天鹅放在一个隔间里，而且还应该使两只天鹅之间的最小距离尽可能的大。可XH0822思考了好久，都不知道这个最大的最小距离是多少，你能不能帮帮他呢？
数据范围:2<=N<=100000, 0<=xi<=10^9, 2<=C<=N

输入

有多组测试数据，以EOF结束。
第一行包含两个整数N和C
后面接着有N行，分别表示xi的位置。（因为输入流可能很多，建议用scanf读取数据）

输出

每组测试数据输出一个整数，即题目中所说的最大的最小值。

输入样例1

5 3
1
2
8
4
9

输出样例1

3

输入样例2

2 2
1 1000000000

输出样例2

999999999

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int a[100005];
int n,c;
bool check(int mid){
	int cnt=1;
	int last=a[0];
	for(int i=1;i<n;i++){
		if(a[i]-last>=mid){
			last=a[i];
			cnt++;
		}
	}
	return cnt>=c;
}
int main(){
	
	while(scanf("%d%d",&n,&c)!=EOF){
		for(int i=0;i<n;i++){
			scanf("%d",&a[i]);
		}
		sort(a,a+n);
		int L=0,R=0x7fffffff;
		int ans=0;
		while(L<=R){
			int mid=L+(R-L)/2;
			if(check(mid)){
				ans=mid;
				L=mid+1;
			}else{
				R=mid-1;
			}
		}
		printf("%d\n",ans);
	}
}

稍微麻烦一点的（HDU4004）

青蛙举行了运动会，要求青蛙跳跃小河。河流宽度为 L (1<= L <= 1000000000). 河里会有 n 个石头沿着垂直于河岸的直线排成一排，青蛙以跳到石头上，然后再次跳跃。青蛙最多能够跳 m 次；现在青蛙们想知道他们最少应该有多大的跳跃能力才能够到达河对岸？

Input

多组数据；

每行输入 L，n，m；

接下来输入n个数，代表第 i 个石头距离开始位置的距离，两个石头不可能出现在一起。

Output

输出一个数，代表至少需要的跳跃距离（最小的最大跳跃能力）；

Sample Input

6 1 2
2
25 3 3
11 
2
18

Sample Output

4
11

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int L, n, m;
int a[500005];
bool check(int mid) {
	if (mid * m < L) {////当前跳M次能跳的距离小于河宽L，不合法 
		return 0;
	}
	int last = 0;
	int cnt = 0;
	for (int i = 0; i <= n; i++) {
		if (a[i + 1] - a[i] > mid) {////如果两块石头距离大于当前单步能跳的最远距离，不合法
			return 0;
		}
		if (a[i] - last <= mid&&a[i+1]-last>mid) {//如果你前面两个都在能力范围之内，跳过当前这个，跳更远的哪个（贪心）
			cnt++;
			last = a[i];
		}
	}
	if (a[n + 1] - last > mid) {//判断一下最后一步
		return 0;
	}
	else {
		cnt++;
	}
	return cnt <= m;
	
}
int main() {
	while (scanf("%d%d%d", &L, &n, &m) != EOF) {
		for (int i = 1; i <= n; i++) {
			scanf("%d", &a[i]);
		}
		a[n+1] = L;
		sort(a, a + n+1);
		int left = 0, right = L;
		int ans = 0;
		while (left <= right) {
			int mid = left + (right - left) / 2;
			if (check(mid)) {
				ans = mid; 
				right = mid-1;
				
			}
			else {
				left = mid + 1;
			}
		}
		printf("%d\n", ans);
	}
}

曾经的错题（HDU-4190）

马上就到大选的日子了，小 O 作为负责人，负责准备大选用的投票箱；现在只有 M 个投票箱；
参加大选的有 N 个城市，每个城市都有固定的人数，分别为 a1, a2, ··· aN，每个人只能投一票；并且要求每个城市至少有一个投票箱；
每个投票箱的容量无限；
现在小 O 的任务是合理分配投票箱，使得各个投票箱中的 票数最大值 尽可能小。

Input

第一行两个数，N (1<=N<=500,000) 和 M (N<=M<=2,000,000)，分别对应题中叙述的含义；
接下来 N 行，a1, a2, ···，aN (1<=ai<=5,000,000)，分别表示每个城市的人数；
多组输入，遇到 -1 -1 结束

Output

各个投票箱中的 票数最大值 的最小值。

Sample Input

2 7
200000
500000

4 6
120
2680
3400
200

-1 -1

Sample Output

100000
1700

Hint

第一个样例，分配方式为 2, 5，每个投票箱的票数都是 100000；
第二个样例，分配方式为 1, 2, 2, 1，各个投票箱的票数为 120, 1340, 1340, 1700, 1700, 200；最大值为 1700；除此之外，没有哪种分配方式能使得投票箱的票数最大值比 1700 还小。

#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
int box[500000+5];
int n,b,Max=-0x7fffffff;
bool check(int mid){
	int sum=0;
	for(int i=0;i<n;i++){
		sum+=ceil(box[i]*1.0/mid);//使用ceil函数。ceil(x)返回的是大于x的最小整数。
	}
	if(sum<=b){
		return 1;
	}else{
		return 0;
	}
}
int main(){
	while(scanf("%d%d",&n,&b)!=EOF){
		if(n==-1&&b==-1){
			break;
		}
		Max=-0x7fffffff;
		for(int i=0;i<n;i++){
			scanf("%d",&box[i]);
			Max=max(box[i],Max);
		}
		int L=1,R=Max,ans=-1;
		while(L<=R){
			int mid=L+(R-L)/2;
			if(check(mid)){
				ans=mid;
				R=mid-1;
			}else{
				L=mid+1;
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}

check函数那块想了好久，最后想经典的分苹果例子，瞬间秒懂~

最后一个！（HDU1969）

我的生日要到了！根据习俗，我需要将一些派分给大家。我有 N 个不同口味、不同大小的派。有 F 个朋友会来参加我的派对，每个人会拿到一块派 (必须一个派的一块，不能由几个派的小块拼成；可以是一整个派)。

我的朋友们都特别小气，如果有人拿到更大的一块，就会开始抱怨。因此所有人拿到的派是同样大小的 (但不必是同样形状的)，虽然这样有些派会被浪费，但总比搞砸整个派对好。当然，我也要给自己留一块，而这一块也要和其他人的同样大小。

请问我们每个人拿到的派最大是多少？每个派都是一个高为 1，半径不等的圆柱体。

输入

首先输入一个整数 T，表示测试数据的组数。

对于每组测试数据：
第 1 行包含两个正整数 N, F，分别表示派的数量和朋友的数量，满足 1 <= N, F <= 10000。
第 2 行包含 N 个 1 到 10000 之间的整数，表示每个派的半径。

输出

每组测试数据对应一行，输出每个人能得到的最大的派的体积，误差不超过 10^(-3)。

示例输入

3
3 3
4 3 3
1 24
5
10 5
1 4 2 3 4 5 6 5 4 2

示例输出

25.1327
3.1416
50.2655

#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
int n,f;
double Max=-0x7fffffff;
const double PI=acos(-1.0);
const double eps=1e-6;
double pi[10005];
bool check(double mid){
	int cnt=0;
	for(int i=0;i<n;i++){
		cnt+=floor(pi[i]/mid);
	}
	return cnt>=f+1;
}
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&n,&f);
		for(int i=0;i<n;i++){
			scanf("%lf",&pi[i]);
			pi[i]=PI*pi[i]*pi[i];
			Max=max(Max,pi[i]);
		}
		double L=0.0,R=Max,ans=0;
		double mid;
		while(R-L>eps){
			mid=(L+R)/2;
			if(check(mid)){
				ans=mid;
				L=mid;
			}else{
				R=mid;
			}
		}
		printf("%.4f\n",ans);	
	}
}