CF1015C Songs Compression 题解

题目传送门

思路

贪心。

考虑到，如果把 $a_i$ 换成 $b_i$，总重量会减少 $a_i-b_i$。

每次操作找到最大的 $a_i-b_i$，把 $a_i$ 替换成 $b_i$。

所以，我们可以将这些物品按 $a_i-b_i$ 递减的顺序来排序。

排序后，按照从 $1$ 到 $n$ 的顺序替换，直到总重量不超过 $m$ 为止。

程序末尾还要判断一下，当 $a_i$ 全部替换成 $b_i$ 时，是否能装下。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
struct node{int a,b;} a[100010];
bool cmp(node a,node b)
{
	return a.a-a.b>b.a-b.b;
}
int n,m;
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	int sum=0;//sum记录总质量
	for(int i=1;i<=n;i++)
		cin>>a[i].a>>a[i].b,sum+=a[i].a;
		
	if(sum<=m)//特判：此时总重量小于等于m，不需要替换，答案为0
	{
		cout<<0;return 0;
	}
	
	sort(a+1,a+1+n,cmp);//按照b[i]-a[i]递减的顺序排序
	for(int i=1;i<=n;i++)
	{
		sum-=a[i].a-a[i].b;//将a[i]替换成b[i]，总质量减少a[i]-b[i]
		if(sum<=m)//如果总重量小于等于m，说明背包已经能装下。此时替换了i次，直接输出i即可
		{
			cout<<i;return 0;
		}
	}
	cout<<"-1";//所有的数字都换了，仍无法装下，输出-1
	return 0;
}

---