|
|
题目描述
FJ's N (1 ≤ N ≤ 10,000) cows conveniently indexed 1..N are standing in a line. Each cow has a positive integer height (which is a bit of secret). You are told only the height H (1 ≤ H ≤ 1,000,000) of the tallest cow along with the index I of that cow.
FJ has made a list of R (0 ≤ R ≤ 10,000) lines of the form "cow 17 sees cow 34". This means that cow 34 is at least as tall as cow 17, and that every cow between 17 and 34 has a height that is strictly smaller than that of cow 17.
For each cow from 1..N, determine its maximum possible height, such that all of the information given is still correct. It is guaranteed that it is possible to satisfy all the constraints.
题意翻译
FarmerJohn 有n头牛，它们按顺序排成一列。 FarmerJohn 只知道其中最高的奶牛的序号及它的高度，其他奶牛的高度都是未知的。现在 FarmerJohn 手上有R条信息，每条信息上有两头奶牛的序号（a和b），其中b奶牛的高度一定大于等于a奶牛的高度，且a，b之间的所有奶牛的高度都比a小。现在FarmerJohn想让你根据这些信息求出每一头奶牛的可能的最大的高度。（数据保证有解）
输入
Line 1: Four space-separated integers: N, I, H and R
Lines 2..R+1: Two distinct space-separated integers A and B (1 ≤ A, B ≤ N), indicating that cow A can see cow B.
第1行：四个以空格分隔的整数：n，i，h和R（n和R意义见题面; i和 h表示第i头牛的高度为h，他是最高的奶牛）
接下来R行：两个不同的整数a和b（1 ≤a，b≤ n）
输出
Lines 1..N: Line i contains the maximum possible height of cow i.
一共n行，表示每头奶牛的最大可能高度.
样例输入1
9 3 5 5
1 3
5 3
4 3
3 7
9 8
样例输出1
5
4
5
3
4
4
5
5
5
提示/说明
数据范围：
1 ≤ n ≤ 10000 ; 1 ≤ h ≤ 1000000 ; 0 ≤ R ≤ 10000)
标签
普及+/提高 USACO 模拟 前缀和 差分
题目中要求最大的高度，明显的贪心
每头牛都默认最高身高。可以反过来先求必须减去的身高
如样例1
9 3 5 5
1 3
5 3
4 3
3 7
9 8
每头牛都默认高5
经过第一条信息1 3后，区间(1,3)身高都必须减1（贪心策略），因此每头牛的身高为5 4 5 5 5 5 5 5 5
经过第二条信息5 3后，swap(5,3),区间(3,5)身高都必须减1，因此每头牛的身高为5 4 5 4 5 5 5 5 5
经过第三条信息4 3后，swap(4,3),区间(3,4)身高都必须减1，因此每头牛的身高为5 4 5 4 5 5 5 5 5
经过第四条信息3 7后，区间(3,7)身高都必须减1，因此每头牛的身高为5 4 5 3 4 4 5 5 5
经过第三条信息9 8后，swap(9,8),区间(8,9)身高都必须减1，因此每头牛的身高为5 4 5 3 4 4 5 5 5
可以看出，我们求出每个区间，利用前缀和思想求出每头牛应该减去的身高就可以了
大型模拟现场
代码见：https://blog.csdn.net/2301_76204446/article/details/138034054
|
|
发表于 2024-4-21 15:03:07
置顶卡