dalao们帮我康康贪心策略哪里不对
查看原帖
dalao们帮我康康贪心策略哪里不对
677091
MnZnOIer楼主2023/8/2 16:06

20分编译记录,真的要气屎

代码:

#include<bits/stdc++.h>
#define ll unsigned long long
#define dl double
#define st string
#define ch char
#define bl bool
using namespace std;
ll n,sum,sum2,ans,ans2;
struct node{
	ll a,b;
}c[10001];
bool cmp1(node a,node b){
	return a.a<b.a;
	//贪心策略:左手小的排前面 
}
bool cmp2(node a,node b){
	return a.b>b.b;
	//贪心策略:右手大的排后面 
}
int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	cin>>n;
	for(ll i=0;i<=n;i++)cin>>c[i].a>>c[i].b;
	sort(c+1,c+n+1,cmp1);
	sum=c[0].a;
	for(ll i=1;i<=n;i++){
		ans=max(ans,sum/c[i].b);
		sum*=c[i].a;
	}
	//两种贪心策略都做,再求最小值即可 
	sort(c+1,c+n+1,cmp2);
	sum2=c[0].a;
	for(ll i=1;i<=n;i++){
		ans2=max(ans2,sum2/c[i].b);
		sum2*=c[i].a;
	}
	cout<<min(ans,ans2);
	return 0;
}

dalao,help me,求调

2023/8/2 16:06
加载中...