题解：CF1612E Messages

wenhaoran11 · 2026-06-07 20:06:22 · 题解

题解

我们假设 g 表示所有置顶消息的集合。

题意就变成了使 \sum_ {m_i \in g}{} \frac{\min(k_i,t)}{t}。

假设我们已经知道了 t 的值，那么肯定是让 k_i 越大越好，贪心即可。

然后观察力惊人的你发现了 k_i \le 20 的神奇限制，你大胆猜测 t 也是小于等于 20 的，然后过了，考虑证明。

设 b_i 表示按 k_i 的贡献的和由大到小排完序的数组，ans_p 表示 t = p 时的最优解。

首先有 \min(k_i,20) = k_i = \min(k_i,21)，这是显然的。

所以 ans_{20} = \frac{1}{20} \sum_{i = 1}^{20} b_i。

并且 ans_{21} = \frac{1}{21} \sum_{i = 1}^{21} b_i。

而最后那个东西显然是大于等于 0 的，所以证出来 ans_{20} \ge ans_{21}，同理你也可以证明出来 ans_{21} \ge ans_{22} 之类的。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5;
int n,k[N],m[N];
struct node{
    int val,id;
};
node b[N];
struct nodee{
    vector<int> mp;
    double x;
    void clear(){
        x=0;
        mp.clear();
    }
};
nodee ans,tmp;
bool cmp(node x,node y){
    return x.val>y.val; 
}
signed main(){
    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=0;i<N;i++){
            b[i]={0,i};
        }
        for(int i=1;i<=n;i++) b[m[i]].val+=min(t,k[i]);
        sort(b+1,b+N,cmp);
        tmp.clear();
        for(int i=1;i<=t;i++){
            tmp.x+=b[i].val;
            tmp.mp.push_back(b[i].id);
        }
        tmp.x/=t;
        if(tmp.x>ans.x) ans=tmp;
    }
    printf("%lld\n",(long long)ans.mp.size());
    for(int i:ans.mp){
        printf("%lld ",i); 
    }
    return ~(-1);
}