CF1612E. Messages

题目描述

有 \(n\) 个学生，他们只有被提醒时才回去阅读通知，如果被通知次数不超过 \(k_i\)，他们一定会去阅读通知，否则他们每次阅读通知的几率为 \(\frac{k_i}{通知次数}\) ，即阅读的总通知数的期望为 \(k_i\)。

现在对于每一个学生，他们需要阅读标号为 \(m_i\) 的通知，你该在哪几条通知进行提醒，使被阅读的通知数期望最大。

\(1 \le n \le 2 \cdot 10^5\)

\(1 \le m_i \le 2 \cdot 10^5\)

\(1 \le k_i \le 20\)

解题思路

阅读体面发现 \(k_i\) 不超过20，当提醒次数大于20时，期望值肯定小于提醒20次时的期望（因为分母被增大了）。所以我们可以考虑枚举所有1-20的提醒次数。

设提醒次数为 \(t\)

对于每一个学生 \(i\)，提醒 \(m_i\) 对答案期望的贡献分为两种情况。① \(t \le k_i\) ，这时这个通知必定阅读，期望贡献为 \(1\)。② \(k_i < t\) ，这是通知被阅读的概率为 \(\frac{k_i}{t}\)。所以综上，通知被阅读的概率为 \(\frac{min(t,k_i)}{t}\)。

为了使期望最大，我们计算出每一个通知被提醒的期望贡献，并将它们降序排序，选取前 \(t\) 个，得到总期望。

进行20次循环，得到最大的期望，输出答案。

过程中的期望计算涉及分数，我们可以将分子分母分别储存，在比较时通过 \(分母a*分子b < 分母b * 分子a\)的方式进行比较。

代码

#include
using namespace std;
using pii = pair;
const int maxn = 2e5;
int k[maxn + 10];
int m[maxn + 10];
void solve() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> m[i] >> k[i];
	}

	pii ansnum = {0,1};
	vector ans;
	for (int i = 1; i <= 20; i++) {
		vector cnt(maxn);
		vector p;
		for (int j = 1; j <= n; j++) {
			cnt[m[j]] += min(i, k[j]);
		}
		for (int j = 0; j < maxn; j++)
			p.push_back(make_pair(cnt[j], j));
		sort(p.begin(), p.end(), greater());
		pii cur = { 0,i };
		vector anst;
		for (int j = 0; j < i; j++)
			cur.first += p[j].first, anst.push_back(p[j].second);
		if (ansnum.first * cur.second < cur.first * ansnum.second) {
			ansnum = cur;
			ans = anst;
		}
	}
	cout << ans.size() << "\n";
	for (auto i : ans) {
		cout << i << ' ';
	}
	cout << "\n";
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	solve();
	return 0;
}