最高的牛

有 N 头牛站成一行，被编队为 1、2、3…N，每头牛的身高都为整数。

当且仅当两头牛中间的牛身高都比它们矮时，两头牛方可看到对方。

现在，我们只知道其中最高的牛是第 P 头，它的身高是 H ，剩余牛的身高未知。

但是，我们还知道这群牛之中存在着 M 对关系，每对关系都指明了某两头牛 A 和 B 可以相互看见。

求每头牛的身高的最大可能值是多少。

注意：

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

思路

题目要保证每头牛尽可能的高，同时又要满足题目给的m对关系，让他们相互之间能够看得见，两头牛要相互看得见，那么两头牛之间的其他牛的高度就必须小于两头牛，不能相等。既要尽可能的高，又要小于，那么就是比两个牛小1就可以。那么我们该如何处理每一对给出的关系，自己手动手动模拟模拟样例就可以发现，每当给出一组，​​这个区间的数必须全部减1，才能满足，不改变前面已经给出的关系​。把一个区间内的数减1，可以用到差分来做，最后的答案，就是求一个前缀和就是原数组。

题目给的数据可能会重复，所以我们可以用一个哈希表来判断是否出现过。

code:

#include<bits/stdc++.h>
using namespace std;

const int N = 100010;
int n,a[N],p,h,m;
int d[N];//差分数组

int main(){
    scanf("%d%d%d%d",&n,&p,&h,&m);
    set<pair<int,int>> ex;
    d[1]=h;
    while (m -- ){
        int l,r;
        scanf("%d%d",&l,&r);
        if(l>r) swap(l,r);
        if(!ex.count({l,r})){
            ex.insert({l,r});
            d[l+1]--;
            d[r]++;
        }
    }
    for(int i=1;i<=n;i++){
        d[i]+=d[i-1];
        cout<<d[i]<<endl;
    }
    return 0;
}