Tallest Cow（差分的应用）

题目描述

题目链接：

https://ac.nowcoder.com/acm/contest/999/C

题意：
n头奶牛，告诉你最高的那头是第I头和它的高度H，以及R组两头互相看见的牛$A_i$和$B_i$，其中两条牛能互相看见的条件是它们中间的牛都小于它们两个的高度；求n个牛的最大高度。

思考

要让两头牛互相能看见，需要将两头牛中间的牛的高度都减一。
利用差分记录相对高度，起始全为0，由于C[i]最高，所以一定为0；

注意去重！

也许有些细心的小伙伴想到了这个情况，但是其实是不成立的，首先A能看见B,即C<B,其次C能看见D，即C>B，矛盾

AC代码：

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include<stdio.h>
#include<math.h>
#include<map>
#include <utility>
#define Inf 1000000
using namespace std;map<pair<int,int>,bool> ex;
int d[1000010],c[1000100];int main(){int n,i,h,r;cin>>n>>i>>h>>r;while(r--){int x,y;cin>>x>>y;if(x>y) swap(x,y);if(ex[make_pair(x,y)]) continue;d[x+1]--,d[y]++;ex[make_pair(x,y)]=true;}for(int i=1;i<=n;i++){c[i]=c[i-1]+d[i];cout<<c[i]+h<<endl;}
}