二分题目及其总结.

1.银行贷款

题目传送门：P1163
思路：找到函数单调性，进行二分查找。下面是分析。


#include<bits/stdc++.h>
using namespace std; 
double n,m;
int k;
bool find(double x){
	return (pow(1.0/(1.0+x),k)>=1-(n/m)*x);//如果大于 向左查找，反之向右查找 
} 
int main(){
	cin>>n>>m>>k;
	double l=0,r=10;
	while(r-l>=1e-4){ //二分 
		double mid=(l+r)/2;
		if(find(mid)) r=mid;
		else l=mid;
	}
	printf("%.1lf\n",l*100);
	return 0;
}

2.烦恼的高考志愿

题目传送门：P1678
本题的二分查找是直接用STL的lower_bound函数实现的。
主要思路是：对学校的分数进行从小到大排序，然后边输入边查找最小值求和就行 时间复杂度 O(nlogm) 时间ok。下面上代码。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int a[N],m,n,ans;
int main(){
	cin>>m>>n;
	for(int i=1;i<=m;i++)
		cin>>a[i];
	sort(a+1,a+m+1);//排序来时间二分查找 
	for(int i=1,x;i<=n;i++)
	{
		cin>>x;
		int p=lower_bound(a+1,a+m+1,x)-a;//返回查找的位置 
		if(p==1) ans+=abs(a[1]-x);//分三种情况 处在第一个 或最后一个 直接取差值 
		else if(p!=m+1)
		ans+=min(abs(a[p]-x),abs(a[p-1]-x));//取前后两个较小的值. 
		else ans+=abs(a[m]-x);		
	}
	cout<<ans<<endl;
	return 0;
}

3.眼红的Medusa

题目传送门：P1571
我做了三种做法实质一样：法1.利用map映射对数字进行标记。法2.两个数组 + STL lower_bound 法3.两个数组排序+自己写一个 二分查找函数。PS（还是STL map好用)

法1.利用map映射对数字进行标记

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int m,n,a[N];
int main(){
	cin>>n>>m;
 	map<int,int>mp;
 	for(int i=1,x;i<=n;i++)
 		 cin>>a[i];
 	for(int i=1,x;i<=m;i++)
 	{
 		cin>>x;
 		mp[x]=1;
 	}
 	for(int i=1;i<=n;i++)
 		 if(mp[a[i]]) printf("%d ",a[i]);
 	puts("");
 	return 0;
}

法2:两个数组 + STL lower_bound

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int a[N],b[N],n,m;
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=1;i<=m;i++)
		cin>>b[i];
	sort(b+1,b+m+1);
	for(int i=1;i<=n;i++)
		{
			int p=lower_bound(b+1,b+m+1,a[i])-b;
			if(b[p]==a[i])
				printf("%d ",a[i]);
		}
	puts("");
	return 0;
}

法3：自己写二分

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int a[N],b[N],n,m;
bool fun(int i){
	 int l=1,r=m;
	 while(l<=r)
	 {
	 	 int mid=(l+r)/2;
	 	 if(a[i]==b[mid]) return 1;
	 	 else if(l==r) return 0;//如果二分到结束还没有找到 返回0 
	 	 else if(a[i]>b[mid]) l=mid+1;
	 	 else if(a[i]<b[mid]) r=mid-1;
	 }
	 return 0;//如果跳出循环也没找到 返回0 
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=1;i<=m;i++)
		cin>>b[i];
	sort(b+1,b+m+1);
	for(int i=1;i<=n;i++)
		if(fun(i)) printf("%d ",a[i]);
	return 0;
}