题解：P11349 [NOISG2024 Finals] Problem Setter

shaun2000 · 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记录