【差分】POJ 3263 Tallest Cow

题目大意

POJ链接

给出\(n\)头牛的身高，和\(m\)对关系，表示牛\(a[i]\)与\(b[i]\)可以相互看见。已知最高的牛为第\(p\)头，身高为\(h\)。

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

（老姚的翻译好像改变量名了昂，但是无所谓）

输入格式

第一行四个整数\(n,p,h,m\)，表示见题意，

接下来\(m\)行，每行两个正整数表示\(a[i],b[i]\)。

输出格式

\(n\)行整数表示每头牛的最大可能身高。

数据范围

\(1\le n\le 10000,1\le h\le 1000000,0\le m\le 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[i],b[i]\)之间可以相互看见，那么这两头牛之间的牛肯定都要比这两头牛要矮。把他们的身高都减去1即可。至于最后怎么算高度，就是相对于\(p\)的，用差分数组。

代码

#include <iostream>

#include <algorithm>

#include <map>

using namespace std;

const int maxn=10000+10;

int n,p,h,m;

map<pair<int,int>,int> vis;//和容易题那题一样依然可能有重复条件

int c[maxn],d[maxn];

int main(){

    scanf("%d%d%d%d",&n,&p,&h,&m);

    for(int i=1;i<=m;i++){

        int a,b;

        scanf("%d%d",&a,&b);

        if(a>b)swap(a,b);//有的条件的顺序反了

        if(vis[make_pair(a,b)])continue;

        vis[make_pair(a,b)]=1;

        d[a+1]--;d[b]++;

    }

    for(int i=1;i<=n;i++){

        c[i]=c[i-1]+d[i];

        printf("%d\n",h+c[i]);

    }

    return 0;

}

巴特西