E. Messages

假设当前置顶了$x\{x\}$条信息，学生$i\{i\}$对信息$m_i\{m\_i\}$的期望贡献如下：

如果$m_i\{m\_i\}$没被置顶，那么贡献为0

如果$m_i\{m\_i\}$被置顶了，那么选出$1\{1\}$条信息包含$m_i\{m\_i\}$的概率为$\frac{1}{x}\{\backslash frac\{1\}\{x\}\}$，选出$k_i\{k\_i\}$条信息包含$m_i\{m\_i\}$的概率为$\frac{\min (k_i,x)}{x}\{\backslash frac\{\backslash min(k\_i,x)\}\{x\}\}$

明显的，如果确定了$x\{x\}$，那么每条信息的期望都能确定，取出期望前$x\{x\}$大的信息，就是置顶了$x\{x\}$条信息时能得到的最大期望。

考虑$\frac{\min (k_i,x)}{x}\{\backslash frac\{\backslash min(k\_i,x)\}\{x\}\}$，如果$\mathrm{\forall }{k}_i\{\backslash forall\; k\_i\}$都小于或等于$x\{x\}$，那么当$x\{x\}$增大时，分子不变，那么置顶了$x\{x\}$条信息时能得到的最大期望减小。

所以最多自需要枚举$x\in 1\sim 20\{x\backslash in\; 1\backslash sim\; 20\}$，然后取期望之和最大的那个答案。

code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+7,mod=1e9+7;
struct app{
	int x,y;
	bool operator<(const app& a)const{
		return x>a.x;
	}
}a[maxn];
int m[maxn],k[maxn];
signed main() {
	cin.sync_with_stdio(false), cin.tie(nullptr),cout.tie(nullptr);
	int n;
	cin>>n;
	for(int i=1;i<=n;++i) {
		cin>>m[i]>>k[i];
	}
	vector<int>ans;
	double res=0.0;
	for(int i=1;i<=20;++i) {
		for(int j=1;j<=200000;++j) a[j]={0,j};
		for(int j=1;j<=n;++j) {
			if(k[j]>=i) a[m[j]].x+=i;
			else a[m[j]].x+=k[j];
		}
		sort(a+1,a+200001);
		double tmp=0.0;
		vector<int>v;
		for(int j=1;j<=i;++j) tmp+=a[j].x,v.emplace_back(a[j].y);
		tmp/=i;
		if(tmp>res) {
			res=tmp;
			ans=v;
		}
	}
	cout<<ans.size()<<'\n';
	for(auto i:ans) cout<<i<<' ';
	return 0;
}