自动搬运

查看原文

来自洛谷，原作者为

	shaun2000 这个家伙不懒，但什么也没有留下

搬运于2025-08-24 23:06:38，当前版本为作者最后更新于2024-12-26 21:29:52，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

solution

考虑贪心。

由于每一场比赛可以投无限道题目，所以对于每一道题目，我们一定是把它投给满足质量要求的增加满意度最多的比赛，如果亏就不投。所以可以先处理出质量为 $i$ 的比赛所能提供的最大满意度 $a[i]$ ，又因为一道质量为 $i$ 的题目，一定满足任一一场质量要求为 $j \le i$ 的比赛，所以我们可以通过 $a[i]=\max(a[i] ,a[i-1])$ 处理出一道质量为 $i$ 的题所能得到的最大满意度。最后求出满意度减去每一道题带来的满意度损失的和即为答案。

时间复杂度： $O(c+p)$。

code

#include<bits/stdc++.h>
using namespace std;

int a[1000005];
int main(){
    int c,p;
	scanf("%d%d",&c,&p) ;
	for(int i=1;i<=c;i++)
	{
		int m,s;
		scanf("%d%d",&m,&s);
		a[m]=max(a[m],s);//求出质量为m的比赛的最大满意度
	}
	for(int i=1;i<=1000000;i++)
		a[i]=max(a[i],a[i-1]);//求出质量为i的题能获得的最大满意度
	long long ans=0;//long long
	for(int i=1;i<=p;i++)
	{
		int q,d;
		scanf("%d%d",&q,&d);
		ans+=max(0,a[q]-d);//若亏，则不投
	}
	printf("%lld\n",ans);
   	return 0;
}

ac记录