Educational Codeforces Round 117 (Rated for Div. 2)E. Messages

Topic link ： Please order me

The question

The topic is mainly about a tutor who wants to give $n$ Students sent messages , He can send to all students at the same time $m$ Bar message , Then everyone has something that the tutor wants to send him $m_i$ Information and $k_i$ Number of times to view messages , If the number of messages sent by the professor is less than $k_i$ Words , And this $m$ This message contains what the student wants to see $m_i$ Bar message , Then add one to the number of people who see the news （ Because I must have seen the news ）. If the number of messages sent is greater than $k_i$ , When there is news that the student needs to read , He will be at random $m$ Choose one of the messages $k_i$ Subset of messages , There is a certain probability of seeing the required information , Expectation plus probability times one . Now ask how to choose the message to send so that all students have the greatest expectation of seeing the information they need to see . Output any message set .

Ideas

First, observe the given data range , Found to have $2\ast 10^5$ A student , It's a little bit big . But we found that $k$ Small values , Only $20$ . This shows that we can learn from $k$ It is worth starting to solve this problem . When the expected number of people received is the highest , The number of messages we can send is actually no more than $20$ Of , Because it's bigger than $20$ No one will be 100% likely to receive the information they need , And every additional piece of information , Everyone's expectations will drop before . Therefore, it is bold to guess that the number of messages sent is not greater than $20$ .( Actually, I won't prove ) .

Answer key

Now that you can enumerate information numbers , Then we can enumerate the expectation of the maximum number of recipients for the same information number . In enumerating information numbers $i$ when , For the first $j$ For people who need to receive information , The probability is （ expect ） Namely $\min (1,\frac{k}{i})$ , No more than $1$ It's obvious , about $\frac{k}{i}$ With the following certificates ：

Let's say that a person has checked the number of times $k_i$ Less than the number of messages currently sent n, Then the probability can be solved by the combination number , by $\frac{\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)}{\left(\genfrac{}{}{0ex}{}{n}{k}\right)}$（ The total number of schemes is at $n$ Take whatever you like $k$ strip , The number of schemes that meet the conditions is to get the required information first , And then in $n-1$ Take the rest of the $k-1$ strip ）, Then, the combination number reduction can be expanded to obtain $\frac{k}{n}$.

Then you can sort the largest by bubbling $i$ Information expectations , It is found that the sending quantity is $i$ The expectation of the maximum number of recipients and the corresponding scheme . Finally, compare and take the maximum value among all the numbers sent , Output this scheme .

PS: Why bubble ？ We can find out just to find the biggest 20 Number , Direct full sequence sorting complexity takes off directly , Bubbling can greatly reduce the number of exchanges .

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;
typedef long long ll;
typedef pair<double,int> P;
const int maxn=2e5+5;

int n,u,v,w,xk,mx;
double ans;
P pre[30][30];
struct node{
    
	int m,k;
}t[maxn];
vector<int>vt,cnt[maxn];
ll vs[30];

int main()
{
    
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)
	{
    
		cin>>t[i].m>>t[i].k; mx=max(mx,t[i].m);
		cnt[t[i].m].push_back(t[i].k);
	}
	for(int i=1;i<=20;i++)
	{
    
		for(int j=1;j<=mx;j++)
		{
    
			double tmp=0;
			for(auto k:cnt[j])
			{
    
				tmp+=min(1.0,k*1.0/i);
			}
			int top=i+1; 
			pre[i][top]=P(tmp,j);
			while(pre[i][top]>pre[i][top-1]&&top-1)
			{
    
				swap(pre[i][top],pre[i][top-1]),top--;
			}
		}
	}
	for(int i=1;i<=20;i++)
	{
    
		double tmp=0;
		for(int j=1;j<=i;j++)tmp+=pre[i][j].first;
		if(ans<tmp)ans=tmp,xk=i;
	}
	cout<<xk<<"\n"; 
	for(int i=1;i<=xk;i++)cout<<pre[xk][i].second<<" ";   
	return 0;
}