最小贪吃量 题解

1.题意

点击查看

这是一道难在题目理解的题，所以我们就先把题目梳理一下

菜：N道

甜度：A i || 限制不超过X

咸度：B i || 限制不超过Y

求最少可吃多少菜

2.解题

本人初始代码因题目理解问题Wrong Answer，就不发了吧。

以下是正解

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int TOP=2e5+5;
int n,x,y;
int zong1,zong2;
int a[TOP],b[TOP];
bool cmp(int a,int b)
{
	return a>b;
}
signed main()
{
//	freopen("eat.in","r",stdin);
//	freopen("eat.out","w",stdout);
	int f;
	cin>>n>>x>>y;
	for(f=1;f<=n;f++)
		cin>>a[f];
	for(f=1;f<=n;f++)
		cin>>b[f];
	sort(a+1,a+1+n,cmp);
	sort(b+1,b+1+n,cmp);
//	for(f=1;f<=n;f++)
//		cout<<a[f]<<' '<<b[f]<<endl;
	for(f=1;f<=n;f++)
	{
		zong1+=a[f];
		zong2+=b[f];
		if(zong1>x||zong2>y)
		{
			cout<<f;
			return 0;
		}
	}
	cout<<n;
	return 0;
}

运用贪心，求咸度最大情况下能吃多少菜或甜度最大能吃多少菜。

甜度和咸度相对独立，因为求甜度，咸度最大为多少，即使甜度与咸度被绑定在一道菜中，但只要选择一个顺序，满足其中一个最大，即为正确答案，无关甜咸组合。

所以运用两个排序，分别求出满足甜度最大或咸度最大能吃多少菜，取最小值即可。

诚信做人，请勿抄袭