网硕互联帮助中心本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。
欢迎大家订阅我的专栏：算法题解：C++与Python实现！
附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总
【题目来源】
洛谷：P2879 [USACO07JAN] Tallest Cow S – 洛谷
【题目描述】
FJ 的
N
N
N 头奶牛（
1
≤
N
≤
10
,
000
1 \\le N \\le 10,000
1≤N≤10,000）按编号
1
1
1 到
N
N
N 排成一行。每头奶牛有一个正整数表示的身高（这是个秘密）。现在你只知道最高奶牛的身高
H
H
H（
1
≤
H
≤
1
,
000
,
000
1 \\le H \\le 1,000,000
1≤H≤1,000,000），以及它的编号
I
I
I。
FJ 提供了
R
R
R 条信息（
0
≤
R
≤
10
,
000
0 \\le R \\le 10,000
0≤R≤10,000），每条信息形如“奶牛 17 能看到奶牛 34”。这意味着奶牛 34 的身高不小于奶牛 17 的身高，并且编号在 17 和 34 之间的所有奶牛，其身高都严格小于奶牛 17 的身高。
现在请你计算出对于每一头奶牛（编号从
1
1
1 到
N
N
N），在所有给定信息都成立的前提下，它可能具有的最大身高。
题目保证一定存在满足条件的解。
【输入】
第
1
1
1 行：四个用空格分隔的整数：
N
N
N，
I
I
I，
H
H
H 和
R
R
R。
第
2
2
2 到第
R
+
1
R+1
R+1 行：每行两个不同的整数
A
A
A 和
B
B
B（
1
≤
A
1 \\le A
1≤A,
B
≤
N
B \\le N
B≤N），表示奶牛
A
A
A 能看到奶牛
B
B
B。
【输出】
共
N
N
N 行，第
i
i
i 行输出奶牛
i
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
【核心思想】
问题分析：给定
N
N
N 头奶牛排成一行，已知最高奶牛编号
I
I
I 身高
H
H
H，以及
R
R
R 条"能看到"信息。若
A
A
A 能看到
B
B
B，则
h
e
i
g
h
t
[
B
]
≥
h
e
i
g
h
t
[
A
]
height[B] \\ge height[A]
height[B]≥height[A]，且
A
A
A 与
B
B
B 之间的所有奶牛身高严格小于
h
e
i
g
h
t
[
A
]
height[A]
height[A]。求每头奶牛的最大可能身高。这是一个差分数组 + 区间约束问题，关键在于将"能看到"关系转化为区间高度限制，用差分数组高效处理。
算法选择：
- 差分数组：每条"能看到"信息意味着
(
A
,
B
)
(A, B)
(A,B) 开区间内的所有奶牛身高至少比两端低1
1
1，用差分标记区间减1
1
1 - 去重处理：用 set 存储已处理的区间，避免重复信息导致过度递减
- 前缀和还原：差分数组前缀和得到每头奶牛相对于基准的累计高度调整
关键步骤：
- 读取输入：
N
,
I
,
H
,
R
N, I, H, R
N,I,H,R 和R
R
R 条信息(
A
,
B
)
(A, B)
(A,B) - 处理每条信息：
- 确保
A
<
B
A < B
A<B（排序） - 若
(
A
,
B
)
(A, B)
(A,B) 已在 set 中：跳过（去重） - 否则：
d
i
f
[
A
+
1
]
−
=
1
dif[A+1] \\mathrel{-}= 1
dif[A+1]−=1，d
i
f
[
B
]
+
=
1
dif[B] \\mathrel{+}= 1
dif[B]+=1（区间(
A
,
B
)
(A, B)
(A,B) 内所有奶牛高度减1
1
1）
- 确保
- 前缀和还原（
i
i
i 从2
2
2 到N
N
N）：d
i
f
[
i
]
+
=
d
i
f
[
i
−
1
]
dif[i] \\mathrel{+}= dif[i-1]
dif[i]+=dif[i−1] - 输出：每头奶牛身高 =
H
+
d
i
f
[
i
]
H + dif[i]
H+dif[i]
时间/空间复杂度：
- 时间复杂度：
O
(
R
log
R
+
N
)
O(R \\log R + N)
O(RlogR+N)，set 去重O
(
R
log
R
)
O(R \\log R)
O(RlogR)，前缀和与输出O
(
N
)
O(N)
O(N) - 空间复杂度：
O
(
N
+
R
)
O(N + R)
O(N+R)，差分数组和去重集合
差分区间约束的核心思想：
- "能看到"的约束转化：
A
A
A 能看到B
B
B 意味着(
A
,
B
)
(A, B)
(A,B) 内的奶牛是"视野遮挡物"，它们必须比A
A
A 矮，即这些奶牛的身高上限被降低 - 最大化身高策略：在不影响约束的前提下，让每头奶牛尽可能高。由于
I
I
I 是最高的，其他奶牛的身高由约束决定其最大可能值 - 差分高效区间操作：将
R
R
R 个区间减1
1
1 操作转化为2
R
2R
2R 个单点更新，前缀和一次性还原 - 去重必要性：同一区间被多次提及不应重复约束，否则会导致高度过度降低
- 适用于"区间约束 + 最大化目标值"类问题，核心是将约束转化为差分标记并去重
【算法标签】
#普及 #差分
【代码详解】
#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区间的牛高度减1
dif[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
评论前必须登录！
注册