专栏文章

题解：P14361 [CSP-S 2025] 社团招新 / club（民间数据）

gggc123
P14361题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@minfjahn
此快照首次捕获于
2025/12/02 01:35
3 个月前
此快照最后确认于
2025/12/02 01:35
3 个月前
查看原文

思路

注意到：当最大的一个分组达到了 n2\dfrac{n}{2} 人时，另外第二大的分组一定不大于 n2\dfrac{n}{2} 人。 因此只需要保证最大的一个分组合法即可。
先假设所有人都分配到了各自最喜欢的组，将这一种分配方式设为理想状态。但是，理想状态大多是不合法的状态，因此我们需要找到与理想状态相差最小的最优解。
对于每一个人都有最喜欢的组别和第二喜欢的组别。为了满足最大的分组人数不大于 n2\dfrac{n}{2} 人，就应当把一部分人从最喜欢的组别调整到第二喜欢的组别。将一个人的损失定义为最大的满意度减去第二大的满意度。我们只需要将损失较小的人调走就可以满足总体损失较小，进而推导出最优解。

代码

CPP
#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 1e5 + 5;
int T, n, ans, cnt[5];
pair<int, int> d[5];

// name	表示组名
// sat	表示满意度
// loss	表示调走一个人的损失
struct People {
	int name1, sat1, name2, sat2, loss;
} p[N];

bool cmp(People A, People B) { return A.loss > B.loss; }

signed main() {
	cin.tie(0), cout.tie(0);
	cin >> T;
	while (T--) {
		ans = 0;
		memset(cnt, 0, sizeof cnt);
		cin >> n;
		for (int i = 1; i <= n; i++) {	// 计算最喜欢的组和第二喜欢的组
			cin >> d[1].first >> d[2].first >> d[3].first;
			d[1].second = 1, d[2].second = 2, d[3].second = 3;
			sort(d + 1, d + 4, greater<pair<int, int>>());
			p[i].name1 = d[1].second, p[i].sat1 = d[1].first;
			p[i].name2 = d[2].second, p[i].sat2 = d[2].first;
			p[i].loss = p[i].sat1 - p[i].sat2;
		}
		sort(p + 1, p + 1 + n, cmp);	// 按照损失大小排名
		for (int i = 1; i <= n; i++) {	// 贪心
			if (cnt[p[i].name1] >= n / 2)
				cnt[p[i].name2]++, ans += p[i].sat2;
			else
				cnt[p[i].name1]++, ans += p[i].sat1;
		}
		cout << ans << "\n";
	}
	return 0;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...