欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！
专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。
适合人群：
- 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
- 希望系统学习C++/Python编程的初学者
- 想要提升算法与编程能力的编程爱好者
附上汇总贴：USACO历年白银组真题解析 | 汇总-CSDN博客
P2879
【题目来源】
洛谷：[P2879 USACO07JAN] Tallest Cow S - 洛谷
【题目描述】
FJ 的 \(N\) 头奶牛（\(1 \le N \le 10,000\)）按编号 \(1\) 到 \(N\) 排成一行。每头奶牛有一个正整数表示的身高（这是个秘密）。现在你只知道最高奶牛的身高 \(H\)（\(1 \le H \le 1,000,000\)），以及它的编号 \(I\)。
FJ 提供了 \(R\) 条信息（\(0 \le R \le 10,000\)），每条信息形如“奶牛 17 能看到奶牛 34”。这意味着奶牛 34 的身高不小于奶牛 17 的身高，并且编号在 17 和 34 之间的所有奶牛，其身高都严格小于奶牛 17 的身高。
现在请你计算出对于每一头奶牛（编号从 \(1\) 到 \(N\)），在所有给定信息都成立的前提下，它可能具有的最大身高。
题目保证一定存在满足条件的解。
【输入】
第 \(1\) 行：四个用空格分隔的整数：\(N\)，\(I\)，\(H\) 和 \(R\)。
第 \(2\) 到第 \(R+1\) 行：每行两个不同的整数 \(A\) 和 \(B\)（\(1 \le A\), \(B \le N\)），表示奶牛 \(A\) 能看到奶牛 \(B\)。
【输出】
共 \(N\) 行，第 \(i\) 行输出奶牛 \(i\) 的最大可能身高。
【输入样例】
9 3 5 5
1 3
5 3
4 3
3 7
9 8
【输出样例】
5
4
5
3
4
4
5
5
5
【算法标签】
《洛谷 P2879 Tallest Cow》 #模拟# #哈希hashing# #前缀和# #差分# #USACO# #2007#
【代码详解】
#include <bits/stdc++.h>
using namespace std;int N; // 牛的数量
int I; // 初始高度
int H; // 基准高度
int R; // 观察次数
int dif[10005]; // 差分数组，记录高度变化
set<pair<int, int> > s; // 用于去重的集合，存储已处理的区间int main()
{// 输入牛的数量、初始高度、基准高度和观察次数cin >> N >> I >> H >> R;// 处理每个观察记录for (int i = 1; i <= R; i++){int A, B; // 观察到的两头牛的编号cin >> A >> B;// 确保A是较小的编号，B是较大的编号if (A > B){swap(A, B);}// 检查是否已处理过相同的区间（去重）if (s.count({A, B}) != 0){continue; // 跳过重复的观察记录}// 将区间加入集合，标记为已处理s.insert({A, B});// 差分数组操作：A+1到B-1区间的牛高度减1dif[A + 1]--; // 从A+1位置开始高度减少dif[B]++; // 到B位置结束高度减少}// 计算前缀和，将差分数组转换为实际高度变化for (int i = 2; i <= N; i++){dif[i] += dif[i - 1];}// 输出每头牛的最终高度for (int i = 1; i <= N; i++){cout << H + dif[i] << endl;}return 0;
}
【运行结果】
9 3 5 5
1 3
5 3
4 3
3 7
9 8
5
4
5
3
4
4
5
5
5