COCI 2014.11.29 T4 题解

题目理解

我们有 $N$ 名选手，已知他们前两轮的分数 $(a_i, b_i)$，第三轮分数 $c_i$ 未知（范围 $[0,650]$）。

重要约束：如果选手 $A$ 前两轮分数都严格高于选手 $B$，那么 $A$ 的第三轮分数必须至少等于 $B$ 的第三轮分数。

排名规则：按三轮总分 $S_i = a_i + b_i + c_i$ 降序排列，同分则同名次，下一个分数更低的选手排名顺延。

要求对每个选手，计算在满足约束条件下可能获得的最好排名和最差排名。

问题转化

设选手 $i$ 的排名为 $r_i$。

约束条件的理解

约束条件实际上定义了一个二维偏序关系：

• 如果 $(a_i > a_j)$ 且 $(b_i > b_j)$，那么必须有 $c_i \ge c_j$

这意味着第三轮的分数分配必须与二维平面上的支配关系保持一致。

核心思路

最好排名的计算

为了获得最好排名，我们希望：

• 自己的第三轮分数尽量高（取最大值 650）
• 竞争对手的分数尽量低

关键观察：能够严格支配当前选手 $i$ 的人（即前两轮分数都更高的人），根据约束条件，他们的第三轮分数必须 $\ge c_i$。当我们取 $c_i = 650$ 时，这些人的第三轮分数也至少是 650，所以他们的总分一定不低于我们。

因此，最好排名就是：

$$\text{最好排名} = 1 + \text{严格支配当前选手的人数}$$

最差排名的计算

为了获得最差排名，我们希望：

• 自己的第三轮分数尽量低（取最小值 0）
• 竞争对手的分数尽量高

关键观察：被当前选手 $i$ 严格支配的人（即前两轮分数都更低的人），根据约束条件，他们的第三轮分数必须 $\le c_i$。当我们取 $c_i = 0$ 时，这些人的第三轮分数也最多是 0。

因此，最差排名就是：

$$\text{最差排名} = N - \text{被当前选手严格支配的人数}$$

算法实现

高效计算支配关系

由于分数范围很小（$0$ 到 $650$），我们可以用二维前缀和/后缀和技巧。

代码中的实现：

1. 初始化计数数组：

vector<vector<int>> cnt(MAXSC + 2, vector<int>(MAXSC + 2, 0));
for (auto &p : players) {
    cnt[p.first][p.second]++;
}

2. 计算后缀和求最好排名： suf[x][y] 表示第一轮 $\ge x$ 且第二轮 $\ge y$ 的人数

for (int x = MAXSC; x >= 0; x--) {
    for (int y = MAXSC; y >= 0; y--) {
        suf[x][y] = cnt[x][y] + suf[x + 1][y] + suf[x][y + 1] - suf[x + 1][y + 1];
    }
}
// 最好排名 = 严格支配的人数 + 1
best_rank = suf[a + 1][b + 1] + 1;

3. 计算前缀和求最差排名： pre[x][y] 表示第一轮 $\le x$ 且第二轮 $\le y$ 的人数

for (int x = 0; x <= MAXSC; x++) {
    for (int y = 0; y <= MAXSC; y++) {
        pre[x][y] = cnt[x][y];
        if (x > 0) pre[x][y] += pre[x - 1][y];
        if (y > 0) pre[x][y] += pre[x][y - 1];
        if (x > 0 && y > 0) pre[x][y] -= pre[x - 1][y - 1];
    }
}
// 最差排名 = N - 被严格支配的人数
worst_rank = n;
if (a > 0 && b > 0) {
    worst_rank -= pre[a - 1][b - 1];
}

样例分析

样例1

输入：
5
250 180
250 132
220 123
132 194
220 105

输出：
1 3
1 3
3 5
1 5
3 5

解释：

• 第1个选手：最好情况没人严格支配他，排第1；最差情况有2个人总分可能超过他，排第3
• 第3个选手：最好情况有2个人严格支配他，排第3；最差情况有4个人总分可能超过他，排第5

样例2

输入：
10
650 550
550 554
560 512
610 460
610 456
650 392
580 436
650 366
520 456
490 456

输出：
1 4
1 8
2 8
2 7
2 9
1 10
4 10
1 10
5 10
5 10

复杂度分析

• 时间复杂度：$O(N + 650^2)$，其中 $650^2$ 是常数
• 空间复杂度：$O(650^2)$

算法标签

• 二维偏序
• 前缀和与后缀和
• 支配关系计数
• 最优化分析

总结

本题的关键在于：

1. 理解约束条件对应的二维偏序关系
2. 将排名问题转化为支配关系的计数问题
3. 利用分数范围小的特点，使用二维前缀和/后缀和高效计算

这种将组合优化问题转化为几何问题，并用前缀和技巧加速计算的方法，在竞赛编程中非常实用。