题目链接

http://poj.org/problem?id=3263

解题思路

选定的一对牛之间的牛的高度都要减一，差分一下，因为最高的为h，所以最后输出差分数组的前缀和，每次输出+h，同时注意判断当前遍历到的这对牛是否已经访问过，若已经访问过，会进行多余的差分操作，使得每个牛并不是尽可能的高。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
typedef pair<int,int> pii;


map<pii,bool> vis;
int n,p,h,r,a,b,d[N];
int main()
{
    cin>>n>>p>>h>>r;
    for(int i=1;i<=r;i++)
    {
        cin>>a>>b;
        if(a>b) swap(a,b);
        if(vis[pii(a,b)]) continue;
        d[a+1]--,d[b]++;
        vis[pii(a,b)]=true;
    } 
    for(int i=1;i<=n;i++)
    {
        d[i]+=d[i-1];
        cout<<h+d[i]<<endl;
    }

    return 0;
}

总结

好牛逼