题解 | #Messages#

【Messages】

定义$X={\sum }_i^n{x}_{i}X=\backslash sum\_\{i\}^nx\_i$为读到需要的信息的学生的数量，其中$x_{i}x\_i$为第$ii$个学生是否读到自己需要的信息，如果读到就为$11$，否则为$00$。

根据期望的可加性可知:

对于每一个$\mathbb{E}(x_i)\backslash mathbb\{E\}(x\_i)$来说：

故:

若顶置的消息集合为: ，则：

因为我们要选取一个集合$UU$使得期望$\mathbb{E}(X)\backslash mathbb\{E\}(X)$最大，所以当$tt$固定时，我们可以贪心的选取集合$UU$。

又因$1\le k_i\le 201\backslash le\; k\_i\backslash le\; 20$，故当$n\ge t>20n\backslash ge\; t>\; 20$时，$P_i=\frac{k_i}{t}P\_i=\backslash frac\{k\_i\}\{t\}$：

需要先将$k_{i}k\_i$的值排序并做前缀和，然后再枚举$tt$的值。

当$t\le 20t\backslash le\; 20$时，可以暴力枚举。

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, m[N], k[N];

double f(int t) {  // 固定t时的最优选取
    unordered_map<int, double> val;
    for (int i = 1; i <= n; i++) {
        if (t <= k[i])
            val[m[i]] += 1;
        else
            val[m[i]] += (1.0 * k[i]) / t;
    }
    vector<pair<int, double>> vec;
    for (auto it : val) vec.push_back({it.first, it.second});
    sort(vec.begin(), vec.end(),
         [](auto a, auto b) { return a.second > b.second; });

    double sum = 0;
    for (int i = 0; i < min(t, (int)vec.size()); i++) sum += vec[i].second;
    return sum;
}

void print(int t) {
    unordered_map<int, double> val;
    for (int i = 1; i <= n; i++) {
        if (t <= k[i])
            val[m[i]] += 1;
        else
            val[m[i]] += 1.0 * k[i] / t;
    }
    vector<pair<int, double>> vec;
    for (auto it : val) vec.push_back({it.first, it.second});
    sort(vec.begin(), vec.end(),
         [](auto a, auto b) { return a.second > b.second; });

    cout << t << "\n";
    for (int i = 0; i < t; i++) cout << vec[i].first << " ";
}

double maxn = -1;
int res = -1;
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> m[i] >> k[i];

    // 当1 < t <= 20时
    for (int t = 1; t <= 20; t++) {
        double sum = f(t);
        if (sum > maxn) maxn = sum, res = t;
    }

    // 预处理：排序，前缀和
    unordered_map<int, double> val;
    for (int i = 1; i <= n; i++) val[m[i]] += k[i];
    vector<pair<int, double>> vec;
    for (auto it : val) vec.push_back({it.first, it.second});
    sort(vec.begin(), vec.end(),
         [](auto a, auto b) { return a.second > b.second; });
    for (int i = 1; i < vec.size(); i++) vec[i].second += vec[i - 1].second;

    // 当t > 20时
    for (int t = 21; t <= vec.size(); t++) {
        double tmp = 1.0 * vec[t - 1].second / t;
        if (tmp > maxn) maxn = tmp, res = t;
    }

    print(res); // 输出结果

    return 0;
}