CF1612E(概率,独立贡献计算+枚举)
题目
Monocarp 是 \(n\) 个学生的导师。现在有很多条消息,Monocarp 希望第 \(i\) 个学生阅读编号为 \(m_i\) 的消息。他需要把一些消息置顶,因为学生只会阅读置顶的消息。
学生 \(i\) 有一个属性 \(k_i\)。如果你置顶了 \(t\) 条消息,若 \(t\le k_i\), 该学生会阅读所有置顶消息;否则,该学生会从置顶的 \(t\) 条消息中随机选 \(k_i\) 条阅读。
你需要求出在使得第 \(i\) 名学生阅读到第 \(k_i\) 条消息的 \(i\) 的数量的期望值最大时,你应该置顶哪些消息。如果有多个答案,输出任意一种。
\(k_i \le 20\)
思路
由于 \(k_i\) 非常小,可以猜测总的置顶数应该也不大,也就是可以枚举的。于是记 \(tot\) 为总的置顶数。
对每个信息考虑,可以写出每个信息 \(m\) 的贡献是 \(\sum_i^n \frac{min(k[i], tot)}{tot},where~~ \exist c_j,c_j=m\) 这里 \(c_j\) 是答案序列中的某一项。
可以发现,它只和自己有关,不同信息之间彼此独立。
于是我们就可以分别计算每个信息的单点贡献,之后取最大的作为答案。
最后,试着证明一下总置顶数不会太大的正确性。我们设 \(w\) 为 \(tot=20\) 时每个人的贡献序列。\(w_i = \frac{min(k[i],tot)}{tot}=\frac{k[i]}{tot}\) 。所以当 \(tot > 20\) 时, \(w\) 不再发生变化。
我们设 \(ans_{20}\) 是 \(tot = 20\) 时的答案,并让 \(w\) 按降序排序,考虑 \(ans_{21}\)。有
\(ans_{20} = \sum_{i=1}^{20}w_i/20\)
\(ans_{21}=\sum_{i=1}^{21}w_i/21\)
作差后易得, \(ans_{20} \ge ans_{21}\)。同理可证其他 \(tot > 20\) 的情况。
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
#include<bitset>
#include<queue>
#include<map>
#include<stack>
#include<string>
#include<random>
#include<cassert>
#include<functional>
#include<iomanip>
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3fll
#define endl '\n'
#define ll long long
// #define int long long
#define SZ(x) (int)x.size()
#define rep(i,a,n) for(int i = (a);i <= (n);i++)
#define dec(i,n,a) for(int i = (n);i >= (a);i--)
using namespace std;
using PII = pair<int,int>;
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand() % x;}
const int N =10 + 2e5 ,mod=1e9 + 7;
const int MAX = 2e5;
int k[N], m[N], n;
PII w[N];
void solve()
{
cin >> n;
for(int i = 1;i <= n;i ++) cin >> m[i] >> k[i];
double mx = 0;
vector<int> Ans;
for(int tot = 1;tot <= min(20, n);tot ++) {
memset(w, 0, sizeof w);
for(int i = 1;i <= n;i ++) {
w[m[i]].first += min(k[i], tot);
w[m[i]].second = m[i];
}
nth_element(w + 1, w + tot, w + MAX + 1, greater<PII>());
int res = 0;
vector<int> ans;
for(int i = 1;i <= tot;i ++) {
res += w[i].first;
ans.emplace_back(w[i].second);
}
if(1. * res / tot > mx) {
mx = 1. * res / tot;
Ans = ans;
}
}
cout << SZ(Ans) << endl;
for(auto x : Ans) cout << x << " ";
cout << endl;
}
signed main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//int T;cin>>T;
//while(T--)
solve();
return 0;
}
标签:概率,20,CF1612E,int,tot,枚举,ans,include,define
From: https://www.cnblogs.com/Mxrush/p/16826669.html