[USACO07JAN] Tallest Cow S

题目解析

问题分析

题目要求求出每头奶牛的最大可能身高。

已知条件：

第 $I$ 头奶牛是最高的，身高为 $H$ 。
$R$ 条关系：奶牛 $A$ 能看到奶牛 $B$ 。
- 这意味着： $A$ 和 $B$ 之间的所有奶牛（不包括 $A$ 和 $B$ ），身高都严格小于 $\min(A, B)$ 的身高。
- 同时题目隐含：为了让大家尽可能高，我们可以假设 $A$ 和 $B$ 的连线“紧贴”着中间奶牛的头顶，也就是说，中间的奶牛仅仅比“挡住视线”的高度矮 1 单位即可。
核心转化

我们可以把每一条关系 $(A, B)$ 看作是对区间 $(A, B)$ （即下标 $A+1$ 到 $B-1$ ）施加的一个“压制”。

初始时，假设所有奶牛的身高都是最高值 $H$ 。
每出现一条关系 $(A, B)$ （假设 $A < B$ ），为了满足“中间的牛比两边的矮”，且要求身高尽可能大，我们只需要将区间 $[A+1, B-1]$ 内的所有奶牛身高减 $1$ 即可。
如果有多个区间重叠（例如 $(1, 5)$ 和 $(2, 4)$ ），这种“减 1”的操作是累加的。
- 比如 $(1, 5)$ 让 $2, 3, 4$ 号牛身高减 1。
- $(2, 4)$ 让 $3$ 号牛身高再减 1。
- 最终 $3$ 号牛比最高身高矮 2。
算法选择：差分数组

我们需要对区间进行多次“减 1”操作，最后查询每个位置的值。这是差分数组的典型应用场景。

定义差分数组 D。
对于区间 $[L, R]$ 的减 1 操作：
- D[L] -= 1
- D[R+1] += 1
在本题中，对于关系 $(A, B)$ ，受影响区间是 $[A+1, B-1]$ 。
- D[A+1] -= 1
- D[B] += 1 （因为 $B-1+1 = B$ ）
最后求前缀和，第 $i$ 头奶牛的身高就是 $H + \sum_{k=1}^{i} D[k]$ 。

4. 细节处理

去重：输入可能会包含重复的关系（例如多次输入 1 3），或者顺序不同但等价的关系（1 3 和 3 1）。我们需要使用 map 或 set 对关系进行去重，避免重复减 1。
区间合法性：如果 $A$ 和 $B$ 相邻（例如 1 2），中间没有牛，不需要进行操作。

复杂度分析

时间复杂度： $O(R \log R + N)$ 。
- 处理 $R$ 条关系，每次使用 map 查询去重及其插入操作为 $O(\log R)$ 。
- 最后遍历一次数组计算前缀和为 $O(N)$ 。
- 给定 $N, R \le 10000$ ，该复杂度完全可以通过。
空间复杂度： $O(N + R)$ 。
- 数组 c 占用 $O(N)$ 。
- Map visited 占用 $O(R)$ 。

总结

这道题巧妙地利用了“最大可能身高”这一条件，将复杂的几何/逻辑约束转化为了简单的区间减法问题，进而使用差分数组在线性时间内解决。

代码

cpp

/**
 * Author by Rainboy blog: https://rainboylv.com github : https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * date: 2026-01-13
 * Problem: P2879 [USACO07JAN] Tallest Cow S
 * Algorithm: Difference Array (差分数组)
 */

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

// 差分数组
// c[i] 表示第 i 个数相对于前一个数的增量（在本题逻辑中用于累积减少量）
int c[10005]; 

// 用于去重，记录已经处理过的关系
// key: pair<int, int>, value: bool
map<pair<int, int>, bool> visited;

int main() {
    // 优化 I/O 效率
    ios::sync_with_stdio(false);
    cin.tie(0);

    int N, I, H, R;
    // N: 奶牛数, I: 最高奶牛编号, H: 最高身高, R: 关系数
    if (!(cin >> N >> I >> H >> R)) return 0;

    for (int i = 0; i < R; ++i) {
        int a, b;
        cin >> a >> b;
        
        // 保证 a < b，方便处理区间
        if (a > b) swap(a, b);
        
        // 如果 a 和 b 是相邻的，中间没有奶牛，不需要处理
        // 例如 1 和 2，中间区间为空
        if (a + 1 >= b) continue;

        // 去重：如果这对关系已经处理过，直接跳过
        if (visited[{a, b}]) continue;
        visited[{a, b}] = true;

        // 核心逻辑：差分数组更新
        // 也就是区间 [a+1, b-1] 的全体数值 -1
        // 根据差分数组定义: 
        // D[L] -= 1
        // D[R+1] += 1
        // 这里 L = a+1, R = b-1 -> R+1 = b
        c[a + 1] -= 1;
        c[b] += 1;
    }

    // 计算前缀和并输出
    // current_reduction 表示当前位置相对于最高身高 H 减少了多少
    int current_reduction = 0;
    for (int i = 1; i <= N; ++i) {
        current_reduction += c[i];
        // 最终身高 = 最高身高 + 累积的减少量
        // (注意 current_reduction 是负数或0)
        cout << H + current_reduction << "\n";
    }

    return 0;
}

[USACO07JAN] Tallest Cow S

目录

题目解析

复杂度分析

总结

代码