题解：CF1082C Multi-Subject Competition

OIerJiang_1017 · 2024-12-18 14:22:07 · 题解

CF1082C 题目传送门

题目大意

有 n 个人分成 m 组，组编号从 1 到 m，第 i 个人属于第 s_i 组，能力值为 r_i。你可以任选一些组，在这些组中选择相同数目的人，使得所选的人的能力值总和最大。

解决思路

建立三个数组：b,cnt,yes。其中：

因为只选择前 i 强的人，所以该组最多能给贡献 yes[cnt[a[i].s]]，因此只枚举前 i 强的人，每次更新即可。

代码展示

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1e5 + 10;
int n, m, ans, maxn;
int b[N], cnt[N], yes[N];
//b[a[i].s]记录第s组中前i强中的人的能力和
//cnt[a[i].s]记录第s组在前i强中的人数
//yes[i]记录每组选 $i$ 人的能力最大值
struct node
{
    int s, r;//s记录编号,r记录能力
    bool operator < (const node &tmp) const
    {//重载运算符
        return r > tmp.r;
    }
}a[N];

int main()
{
    scanf("%d%d", &n, &m);//建议scanf,更快
    for(int i = 1; i <= n; i++)
        scanf("%d%d", &a[i].s, &a[i].r);
    sort(a + 1, a + n + 1);//按能力值从大到小排序
    for(int i = 1; i <= n; i++)
    {//核心部分 
        b[a[i].s] += a[i].r;
        cnt[a[i].s]++;
        maxn = max(cnt[a[i].s], maxn);
        if(b[a[i].s] > 0) yes[cnt[a[i].s]] += b[a[i].s];
    }
    for(int i = 1; i <= maxn; i++)
        ans = max(ans, yes[i]);//每次取最大值
    printf("%d\n", ans);//建议printf,更快
    return 0;
}