[数据结构与算法]二分、三分、01分数规划1

例1

给一串n个单调递增的数，有q次询问>=x且<=y的数有多少个。

1<=n<=10^5；1<=q<=50000

认准一种算法，开始解释。解释详见代码，推荐在写代码时找例子试试，不用死记硬背。

为了防止l+r越界 ，可以写成这种形式：mid=l+(r-l)/2;

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=100, inf=0x7fffffff;
int a[maxn],n,l,r,x,y,mid,ansx,ansy;
int main(){
	cin>>n>>x>>y;
	for(int i=1;i<=n;++i)
		cin>>a[i];
	l=1; r=n;
	//>=x
	while(l<r){
		mid=l+(r-l)/2;//防止l+r越界 
		if(a[mid]>=x) r=mid;// 1 2 3，若要大于等于2而mid指向3，可能前面还有更好的答案
		else l=mid+1;//1 2 3，若要大于等于3而mid指向2，就要让l指向mid+1的位置 
	}
	ansx=r;
//	cout<<ansx<<endl;
	l=1; r=n;
	while(l<r){
		mid=l+(r-l)/2+1;//防止l不动 
		if(a[mid]<=y) l=mid;//0 1 2 3，若要小于等于2而mid指向1，可能后面还有更好的答案
		else r=mid-1; 
	}
	ansy=l;
//	cout<<ansy<<endl;
	cout<<ansy-ansx+1;//别忘了加一
	return 0;
} 

binary_search 返回bool，判断是否存在

lower_bound 返回可插入最小位置的迭代器（如lower_bound(a,a+3,4)，其中a为{1,3,3}，则返回可以插入3的迭代器位置：1之后）即查找第一个大于或等于num的数字。

upper_bound?返回可插入最大位置的迭代器（如lower_bound(a,a+3,4)，其中a为{1,3,3}，则返回可以插入3的迭代器位置：最后一个3之后）即第一个大于num的数字。

另外，可在从大到小的排序数组中，重载lower_bound()和upper_bound()：

lower_bound( begin,end,num,greater<type>() ):查找第一个小于或等于num的数字，找到返回该数字的地址，不存在则返回end。

upper_bound( begin,end,num,greater<type>() ):从数组的begin位置到end-1位置二分查找第一个小于num的数字，找到返回该数字的地址，不存在则返回end。

所以上述问题直接用lower_bound-upper_bound就可以得出结果QAQ

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=100, inf=0x7fffffff;
int a[maxn],n,l,r,x,y;
int main(){
	cin>>n>>x>>y;
	for(int i=1;i<=n;++i)
		cin>>a[i];
	cout<<lower_bound(a+1,a+1+n,x)-a<<endl;
	cout<<upper_bound(a+1,a+1+n,y)-a<<endl;
	cout<<upper_bound(a+1,a+1+n,y)-lower_bound(a+1,a+1+n,x);
	return 0;
} 

既然有了函数，啥时候用手写的呢？答案为：二分答案+检验

牛棚

有n个牛棚在x轴上，已知坐标，FJ有C只奶牛，每只必须安排在一个牛棚里，一个牛棚只能容纳一只，但它们会互相攻击，所以要求距离最近的两个牛棚间的距离最大。

2<=n<=100,000

0<=xi<=1,000,000,000

2<=C<=n

利用了二分的思想：通过结果反馈调整答案。在此题中，需要先对枚举出的答案进行试验，如果成功就再试一个更大的答案。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn=100005, inf=0x7fffffff;
int n,c,ans,a[maxn];
int main(){
	cin>>n>>c;
	for(int i=0;i<n;++i)
		scanf("%d",&a[i]);
	sort(a,a+n);
	int mid=1;
	while(1){
		int tot=1, now=a[0];
		for(int i=1;i<n;++i){
			if(a[i]>=now+mid){
				tot++, now+=mid;
				if(tot==c) break;
			}
		}
		if(tot==c){
			ans=tot;
			mid+=1;
			continue;
		}else break;
	}
	cout<<ans;
	
	return 0;
}

3104 -- Drying

刚洗过的衣服有n件。他们每个人在洗涤过程中都有一定水分。每分钟，每件东西所含的水量都会减少1（当然，只有在东西还没有完全干燥的情况下）。当所含的水量变为零时，布会变干并准备好进行包装。

简每分钟都可以选择一件东西在散热器上晾干。散热器非常热，所以这个东西中的水量在这一分钟减少了k（但不小于零——如果这个东西含有少于k的水，那么产生的水量将是零）。

任务是通过有效地使用散热器来最大限度地减少干燥的总时间。当所有衣服都干燥时，干燥过程结束。

1<=n<=100 000? ;1<=a<=10^9? ;1<=k<=10^9

和上一道题类似，二分答案。关键在于如何判断x分钟能否晾干所有衣服。若x分钟可以自然风干，则不管它；若不能，则计算所需吹风机的时间，再与答案进行对比看吹风机时间够不够。

细节问题：

1、实际上当判断需要的吹风机时间时，需要减掉自然风干的时间！另外，还需要转换成double再用ceil上取整。

2、遇到sum这种求和的，应习惯性地检查是否会爆！

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=100005, inf=0x7fffffff;
int n,k,l=1,r,ans,a[maxn];
int jg(int x){
	long long sum=0;// 注意数据范围会爆int！ 
	for(int i=0;i<n;++i){
		if(a[i]>x) 
			sum+=(int)(ceil((a[i]-x)*1.0/(k-1)));
	}
	return sum<=x;
}
int main(){
	scanf("%d",&n);
	for(int i=0;i<n;++i){
		scanf("%d",&a[i]);
		r=max(r,a[i]);
	}
	scanf("%d",&k);
	if(k==1){
		printf("%d",r);
		return 0;
	}
	while(l<=r){
		int mid=(l+r)>>1;
		if(jg(mid)) //若给的时间够了，说明最后找到的答案应该在r的后一个 
			r=mid-1;
		else
			l=mid+1; 
	}
	
	printf("%d",r+1);
	return 0;
}

总结

若出现解决最大或最小值问题，依次考虑：二分、贪心和动态规划。