1. 核心问题分析：每个玩家的排名由调整后的总分决定（洞得分超过 l 则替换为 l），需找到最优 l 使排名最小。排名定义为「调整后总分 ≤ 该玩家总分的玩家数」。
2. 关键观察：l 仅在等于某个玩家的洞得分时，才会改变玩家总分（l 在两洞得分之间时，总分不变）。因此只需枚举「所有玩家的洞得分」和「最大得分+1」（覆盖 l 无穷大的情况）。
3. 高效计算总分：对每个玩家的洞得分排序并预处理前缀和，通过二分查找快速计算任意 l 下的总分（前 k 个洞取原得分和，后 h-k 个洞取 l）。
4. 优化排名计算：对每个候选 l，一次性计算所有玩家的总分，排序后通过二分查找快速得到每个玩家的排名，避免重复计算。

算法步骤

1. 输入读取与预处理：读取玩家数 p 和洞数 h，收集所有洞得分（用于生成候选 l）。
2. 候选 l 生成：对收集的洞得分去重排序，添加「最大得分+1」，得到候选 l 列表 Ls。
3. 排序与前缀和：对每个玩家的洞得分排序，计算前缀和数组（用于快速计算总分）。
4. 枚举候选 l：
   • 对每个 l，计算所有玩家的调整后总分。
   • 排序总分数组，通过二分查找得到每个玩家的排名。
   • 更新每个玩家的最小排名。
5. 输出结果：按输入顺序输出每位玩家的最小排名。

C++ 代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int p, h;
    cin >> p >> h;

    vector<vector<int>> players(p, vector<int>(h));
    set<int> unique_scores;

    // 读取输入并收集所有洞得分（用于生成候选l）
    for (int i = 0; i < p; ++i) {
        for (int j = 0; j < h; ++j) {
            cin >> players[i][j];
            unique_scores.insert(players[i][j]);
        }
    }

    // 生成候选l列表：去重后的洞得分 + 最大得分+1（覆盖l无穷大的情况）
    vector<int> Ls(unique_scores.begin(), unique_scores.end());
    if (!Ls.empty()) {
        int max_l = Ls.back();
        Ls.push_back(max_l + 1);
    } else {
        Ls.push_back(1); // 理论上不可能，因每个洞得分≥1
    }

    // 预处理每个玩家的排序得分和前缀和
    vector<vector<int>> sorted_players(p);
    vector<vector<long long>> pre(p, vector<long long>(h + 1, 0));
    for (int i = 0; i < p; ++i) {
        sorted_players[i] = players[i];
        sort(sorted_players[i].begin(), sorted_players[i].end());
        // 计算前缀和：pre[i][k] 是前k个洞的得分和
        for (int k = 0; k < h; ++k) {
            pre[i][k + 1] = pre[i][k] + sorted_players[i][k];
        }
    }

    vector<int> min_rank(p, p); // 初始化为最差排名（所有玩家都≤自己）

    // 枚举每个候选l，计算所有玩家的排名并更新最小排名
    for (int l : Ls) {
        vector<long long> scores(p);
        // 计算当前l下所有玩家的总分
        for (int i = 0; i < p; ++i) {
            const auto& a = sorted_players[i];
            const auto& pr = pre[i];
            // 找到第一个大于l的洞得分位置k，前k个洞取原得分，后h-k个取l
            int k = upper_bound(a.begin(), a.end(), l) - a.begin();
            scores[i] = pr[k] + (long long)l * (h - k);
        }

        // 排序总分数组，用于快速计算排名
        vector<long long> temp_scores = scores;
        sort(temp_scores.begin(), temp_scores.end());

        // 计算每个玩家的当前排名并更新最小排名
        for (int i = 0; i < p; ++i) {
            long long s = scores[i];
            // 二分查找≤s的元素个数，即当前排名
            int rank = upper_bound(temp_scores.begin(), temp_scores.end(), s) - temp_scores.begin();
            if (rank < min_rank[i]) {
                min_rank[i] = rank;
            }
        }
    }

    // 输出每位玩家的最小排名
    for (int r : min_rank) {
        cout << r << '\n';
    }

    return 0;
}

代码解释

1. 输入处理：读取玩家和洞的数量，存储每个玩家的洞得分，并收集所有洞得分到集合（自动去重）。
2. 候选 l 生成：将集合转为有序列表，添加最大得分+1，确保覆盖所有可能影响排名的 l。
3. 排序与前缀和：对每个玩家的洞得分排序，计算前缀和，为快速计算总分做准备。
4. 总分计算：对每个候选 l，通过二分查找找到得分分界点，利用前缀和计算总分（避免遍历所有洞）。
5. 排名计算：排序当前 l 下的所有总分，通过二分查找快速得到每个玩家的排名，更新最小排名。

时间复杂度

• 预处理：O(p·h log h)（排序每个玩家的洞得分 + 计算前缀和）。
• 候选 l 枚举：O(M·(p log h + p log p))，其中 M 是候选 l 的个数（≤p·h）。
• 整体复杂度：O(p·h log h + p·h·p log p)，适用于常规数据范围（如 p≤1e3、h≤1e3）。

空间复杂度

• 存储玩家得分和前缀和：O(p·h)。
• 候选 l 和总分数组：O(p·h + p)，空间开销可控。