Peter算法小课堂—贪心与二分

发布时间:2023年12月22日

太戈编程655题

题目描述:
有n辆车大甩卖,第i辆车售价a[i]元。有m个人带着现金来申请购买,第i个到现场的人带的现金为b[i]元,只能买价格不超过其现金额的车子。你是大卖场总经理,希望将车和买家尽量多地进行一对一配对,请问最多卖出多少辆车?

贪心

贪心法模板:

比如说:每次挑最便宜的车卖给贫穷的人,……

相信大家第一个想到的思路就是二重for循环,第一层int i=1;i<=m;i++,第二层int j=1;j<=n;j++,时间复杂度O(n^2)。但是一看数据规模,n,m<=200000,也就是运行40000000000,四百亿,几乎不可能。这一下子,大家就想到了传说中的“蠕动区间”。代码来咯,

#include <bits/stdc++.h>
using namespace std;
const int N=200009;
int n,m,a[N],b[N];
int main(){
	freopen("car2.in","r",stdin);
	freopen("car2.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=m;i++) cin>>b[i];
	sort(a+1,a+1+n);
	sort(b+1,b+1+m);
	int cnt=0,i=1,j=1;
	while(i<=n&&j<=m){
		if(a[i]<=b[j]){
			i++;
			j++;
			cnt++;
		}else j++;
	}
	cout<<cnt<<endl;
	return 0;
}

太戈编程656题

题目描述:
有n辆车大甩卖,第i辆车售价a[i]元。有m个人带着现金来申请购买,第i个到现场的人带的现金为b[i]元。你是大卖场总经理,可以将车和买家自由配对。如果买家的现金低于配对车的售价时,你有权力借钱给买家,但是总的借款额度不可以超过f。注意:买家之间不会互相借钱。请问通过你的配对和借款,剩下没买到车的人最少有几人?

二分+贪心

思路:要让没买到车的人最少,相当于要求买到车的人最多。二分枚举答案x,OK函数判断卖出x辆车是否可行(最优化问题→可行性问题),而判断的方法就要用到贪心

bool OK(int x){
	int sum=0;
	for(int i=0;i<=x;i++){
		if(a[i]>b[m-x+i]) sum+=a[i]-b[m-x+i];
		if(sum>f) return 0; 
	}
	return 1;
}

?

int main(){
	freopen("car3.in","r",stdin);
	freopen("car3.out","w",stdout);
	cin>>n>>m>>f;
	for(int i=0;i<n;i++) cin>>a[i];
	for(int i=0;i<m;i++) cin>>b[i];
	sort(a,a+n);
	sort(b,b+m);
	int l=0,r=min(n,m),ans=0;
	while(l<=r){
		int mid=l+(r-l)/2;
		if(OK(mid)) ans=mid,l=mid+1;
		else r=mid-1;
	}
	cout<<m-ans<<endl;
	return 0;
}

太戈编程1662题

自己独立思考……

cin>>n>>d;
for(int i=1;i<=n;i++) cin>>x[i];
sort(x+1,x+n+1);
int cnt=0;
for(int i=1;j=2;i<=n-1;i++){
	while(j<=n&&x[j]-x[i]<d) j++;
	cnt+=j-i-1;
}
cout<<cnt<<endl;

希望这些对大家有用,三连必回

文章来源:https://blog.csdn.net/zhang040818/article/details/135155368
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。