CF2048D 完整题解

一、题目大意

给定 $n$ 个参赛者、$m$ 道题目； 每个参赛者有评分 $a_i$，每道题目有难度 $b_j$。 选手能解决满足 $a_i \ge b_j$ 的所有题目。

对每个 $k\in[1,m]$：

1. 每场竞赛固定用 $k$ 道题，总共能举办 $\left\lfloor \dfrac{m}{k} \right\rfloor$ 场；
2. 选用 $\left\lfloor \dfrac{m}{k} \right\rfloor \cdot k$ 道题分组，剩余题目废弃；
3. Kevin 是第 $1$ 号选手，每场排名定义为：比 Kevin 解题更多的人数 $+1$；
4. 每组 $k$ 道题可以自由划分，求所有场次 Kevin 排名总和的最小值。

二、解题核心思想

1. 弱化无关人员：只有评分严格大于 Kevin 的选手才会影响排名，评分更低的可以直接忽略。
2. 弱化简单题目：难度 $\le$ Kevin 评分的题目，Kevin 必做得出，不会有人比他多做题，不影响排名。
3. 构造代价数组：只保留难度大于 Kevin 的题目，对每道题算出有多少高分选手能做出，记为数组 $c$。
4. 贪心最优分组：把 $c$ 升序排序；对固定 $k$，每连续 $k$ 个分为一组，每组最大值决定该场排名，累加每组最大值$+1$ 即为最小总和。

三、完整AC代码（你原版代码原样嵌入）

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n), b(m);
    
    for (int &x : a) cin >> x;
    for (int &x : b) cin >> x;
    
    int kevin = a[0];
    
    // 只保留比 Kevin 强的人
    vector<int> others;
    for (int i = 1; i < n; i++) {
        if (a[i] > kevin) {
            others.push_back(a[i]);
        }
    }
    sort(others.begin(), others.end());
    
    // 计算 c[i] = 能做出这题的人数
    vector<int> c;
    for (int x : b) {
        if (x > kevin) { // 只有 Kevin 做不出的题才会影响排名
            int cnt = others.end() - lower_bound(others.begin(), others.end(), x);
            c.push_back(cnt);
        }
    }
    
    sort(c.begin(), c.end());
    int sz = c.size();
    
    vector<long long> ans(m + 2, 0);
    for (int k = 1; k <= m; k++) {
        int t = sz / k; // 能分 t 组
        long long sum = 0;
        for (int i = 1; i <= t; i++) {
            sum += c[i * k - 1] + 1;
        }
        ans[k] = sum;
    }
    
    for (int k = 1; k <= m; k++) {
        cout << ans[k] << " ";
    }
    cout << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

四、代码分步解析

1. 输入处理 读入多组测试用例，每组读入参赛人数 $n$、题目数 $m$，以及数组 $a,b$。

2. 筛选强于 Kevin 的选手 取出 $a[0]$ 作为 Kevin 评分，只保留评分严格更大的选手，并排序，方便后续二分查找。

3. 构建代价数组 $c$ 遍历所有题目，只保留难度大于 Kevin 的题目； 用 lower_bound 二分统计能做出该题的高分选手数量，存入 $c$。

4. 贪心计算每个 $k$ 的答案 将 $c$ 升序排序； 对每个 $k$，可以分成 $t=\lfloor sz/k \rfloor$ 组，每组取第 $k,2k\dots$ 位置元素为组内最大值，累加 $c_{pos}+1$ 作为排名总和。

5. 输出答案 依次输出 $k=1\sim m$ 对应的最小排名和。

五、复杂度分析

排序：$O(n\log n + m\log m)$； 二分统计：$O(m\log n)$； 枚举所有 $k$ 求和为调和级数复杂度 $O(m\log m)$； 整体复杂度满足题目 $\sum n,\sum m \le 3\times 10^5$ 数据限制。

六、算法关键点

1. 剔除对排名无影响的弱选手和简单题目；
2. 利用二分快速统计每题影响人数；
3. 排序后连续分组贪心，保证每组最大值最小，从而总和最小。