Awing 最高的牛

科技前沿 • 2025-03-22 11:03 • 阅读 20

大家好，我是讯享网，很高兴认识大家。

题目描述
有 N 头牛站成一行，被编队为1、2、3…N，每头牛的身高都为整数。
当且仅当两头牛中间的牛身高都比它们矮时，两头牛方可看到对方。
现在，我们只知道其中最高的牛是第 P 头，它的身高是 H ，剩余牛的身高未知。
但是，我们还知道这群牛之中存在着 M 对关系，每对关系都指明了某两头牛 A 和 B 可以相互看见。
求每头牛的身高的最大可能值是多少。

接下来M行，每行输出两个整数 A 和 B ，代表牛 A 和牛 B 可以相互看见，数据用空格隔开。

第 i 行输出的整数代表第 i 头牛可能的最大身高。

讯享网

数据范围
1≤N≤10000,
1≤H≤,
1≤A,B≤10000,
0≤M≤10000

输入样例：

9 3 5 5 1 3 5 3 4 3 3 7 9 8

讯享网

输出样例：

讯享网5 4 5 3 4 4 5 5 5

本题的思路很好想，首先假设所有的牛都是最高的，然后给定能看到的对儿，如果他们直接能看到，那么中间的牛肯定要矮一点，使用差分就可得出结论
d[a + 1] ++
d[b]–
意思就是 a 到 b 之间的牛（不包括端点），所有的牛身高都要下降一点。

需要注意的是，可能存在重复的对儿，需要去重，我这里用的 set 加 pair 的去重方式。

#include<iostream> #include<string> #include<algorithm> #include<bits/stdc++.h> #include<stack> #include<set> #include<vector> #include<map> #include<queue> #include<deque> #include<cctype> #include<unordered_set> #include<unordered_map> #include<fstream> #include<cstring> using namespace std; const int N = ; int d[N]; int main() { 
    int n, p, h, m; set<pair<int, int> >st; cin >> n >> p >> h >> m; d[1] = h; for (int i = 0; i < m; i++) { 
    int a, b; cin >> a >> b; if (a > b) { 
    swap(a, b); } if (!st.count({ 
   a, b})) { 
    st.insert({ 
   a, b}); d[a + 1]--; d[b] ++; } } for (int i = 1; i <= n; i++) { 
    d[i] += d[i - 1]; cout << d[i] << endl; } return 0; }

Awing 最高的牛

相关推荐