AcWing 101 最高的牛

AcWing 101 最高的牛

题目描述：

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

输入格式

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

输出格式

一共输出 N行数据，每行输出一个整数。第 i 行输出的整数代表第 i头牛可能的最大身高。

数据范围

1≤N≤10000,1≤H≤1000000,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

注意：

• 此题中给出的关系对可能存在重复

分析：

我们读入一对数据，A和B，之间的所有牛身高都比它们要小，既然要求的是每头牛可能的最大身高，不妨将区间内所有牛的身高都减一，这个操作可以直接用差分数组实现，height[a+1]--,height[b]++不仅将区间内身高都—了，而且即使AB相邻时—和++也相互抵消，相当于没有操作。

注意点：

其一，用set判重，因为读入的数据可能有重复。

其二，读入的数据如果不是A<B那么要用swap交换。

其三，转化为区间问题有几种情况，[A,B]与[C,D]交叉，这是不存在的，[C,D]包含在[A,B]内，（即使一个端点重合也无所谓），还有一种就是互不包含，这几种都可以互不干扰的利用差分计算区间。

其四，这里的第几头牛最高其实没用，将差分数组的第一个元素设置为最高，再递推，即求前缀和即可得到每头牛可能的最大身高。

#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
const int N = 10010;
int height[N];
int main(){int n,p,h,m;cin>>n>>p>>h>>m;height[1] = h;set<pair<int,int> > existed;for(int i = 0;i < m;i++){int a,b;cin>>a>>b;if(a > b)	swap(a,b);if(!unt({a,b})){existed.insert({a,b});height[a+1]--,height[b]++;}}for(int i = 1;i <= n;i++){height[i] += height[i-1];cout<<height[i]<<endl;}return 0;
}