题解：CF1082C Multi-Subject Competition

CF1082C 题目传送门

题目大意

有

n

个人分成

m

组，组编号从

1

到

m

，第

i

个人属于第

s_i

组，能力值为

r_i

。你可以任选一些组，在这些组中选择相同数目的人，使得所选的人的能力值总和最大。

解决思路

建立三个数组：

b,cnt,yes

。其中：

$b[a[i].s]$ 记录第 $s$ 组中前 $i$ 强中的人的能力和；
$cnt[a[i].s]$ 记录第 $s$ 组在前 $i$ 强中的人数；
$yes[i]$ 记录每组选 $i$ 人的能力最大值。

因为只选择前

i

强的人，所以该组最多能给贡献

yes[cnt[a[i].s]]

，因此只枚举前

i

强的人，每次更新即可。

代码展示

CPP

#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;
}

题解：CF1082C Multi-Subject Competition

文章操作

CF1082C 题目传送门

题目大意

解决思路

代码展示

相关推荐

评论

题解：CF1082C Multi-Subject Competition