poj3263 Tallest Cow

题目大意

一群奶牛排成一排。他们身高不同。
现在我们知道：有n头奶牛，第I头的身高最高，为h。
下面给出m组关系，每组关系包含两个数，表示这两个数代表的奶牛可以相互看到（两头奶牛之间的所有奶牛都比这两头奶牛矮才能相互看到）
题目要求我们给出所有n头奶牛的可能最大身高。

题解

我们这里采用差分。
差分数组先初始化0.
既然两头奶牛相互看到是因为他们之间的所有奶牛的身高都比他们矮，那么要求最大值，那么矮的相对值应该最小，因为身高都是整数，那么就在两头奶牛之间所有奶牛的身高都-1.
最后，我们会发现，第I头奶牛的差分数组一定是0.那么所有奶牛的最大身高就是差分数组里的值+h。

坑1

给出的相互看到的关系(x,y)有可能是x>y。要先判定是否需要交换

坑2

看到的关系有可能重复出现，需要用一个map来确定是否出现过。

code

#include <iostream> 
#include <cstdio> 
#include <fstream> 
#include <algorithm> 
#include <cmath> 
#include <deque> 
#include <vector> 
#include <queue> 
#include <string> 
#include <cstring> 
#include <map> 
#include <stack> 
#include <set> 
using namespace std;
inline int read(){
    int num=0;char c=' ';bool flag=true;
    for(;c>'9'||c<'0';c=getchar())
        if(c=='-')
            flag=false;
    for(;c>='0'&&c<='9';num=(num<<3)+(num<<1)+c-48,c=getchar());
    return flag ? num : -num;
}
const int maxn=10020;
int n,I,h,m,a[maxn];
map<pair<int,int>,bool>appear;
void work1(){
    n=read();I=read();
    h=read();m=read();
    for(int i=1;i<=m;i++){
        int x=read();
        int y=read();
        if(x>y)swap(x,y);//坑1 
        if(appear[make_pair(x,y)])continue;
        a[x+1]--;a[y]++;
        appear[make_pair(x,y)]=true;//坑2 
    }
}
void work2(){
    for(int i=1;i<=n;i++)
        a[i]+=a[i-1];
    for(int i=1;i<=n;i++)
        printf("%d\n",a[i]+h);
}
int main(){
    work1();
    work2();
    return 0;
}