题解：CF1612E Messages

· · 题解

题外话

这题开始看错题了，以为大于 t_i 条就直接不读了，以为是红题，结果做法误打误撞对了。

题解

观察数据范围，发现 t_i \le 20，于是考虑从这里入手。

其实发现整道题并没有什么好的转化空间，于是我们试着暴力做一做，发现没有问题，那么接下来证明一下。

设 val_i 为贡献和从大到小排序的数组。

对于 t = 20，期望为 \frac{1}{20} \sum_{i=1}^{20} val_i。

对于 t = 21，期望为 \frac{1}{21} \sum_{i=1}^{21} val_i。

我们发现不同的只有 t = 21 的 val_{21} 和其中乘的系数，所以我们可知两者的差值为 \frac{1}{420} \sum_{i=1}^{20} val_i - \frac{1}{21} val_{21}。

因为贡献是从大到小排序，我们不妨放缩一下，将 val_i 设成 val_{21}。这样两者的差值为 0，又因为对于所有 i \le 20，val_i \ge val_{21}，所以差值一定大于 0，即 t = 20 的情况一定比 t = 21 优。所以说选 20 条一定是最优的，证毕。

代码就很好写了。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int k[200005],m[200005];
struct node
{
    int val,id;
    bool operator < (const node x) const
    {
        return val>x.val;
    }
}cnt[200005];
struct edge
{
    vector<int> mp;
    double x;
    void clear()
    {
        x = 0;
        mp.clear();
    }
}ans,qwq;
signed main()
{
    int n;
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
        scanf("%lld%lld",&m[i],&k[i]);
    for(int t=1;t<=20;t++)
    {
        for(int i=1;i<=200000;i++) cnt[i]={0,i};
        for(int i=1;i<=n;i++) cnt[m[i]].val+=min(t,k[i]);
        sort(cnt+1,cnt+200000+1);
        qwq.clear();
        for(int i=1;i<=t;i++)
        {
            qwq.x+=cnt[i].val;
            qwq.mp.push_back(cnt[i].id);
        }
        qwq.x/=t;
        if(qwq.x>ans.x) ans = qwq;
    }
    printf("%lld\n",ans.mp.size());
    for(auto x:ans.mp)
        printf("%lld ",x); 
}