【poj3263】Tallest Cow(差分数组)

            

problem

给出n头牛的身高,和m对关系(a[i]与b[i]可以相互看见。即他们中间的牛都比他们矮)。已知最高的牛为第p头,身高为h。

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

solution

计算牛的相对大小关系。
第p头最高h,比他矮的最高一定是h-1,,,所以最后每头牛的身高就是,’它比p小多少’+h。
直接减就好了,最后c[p]一定是0,(因为他是最高的嘛)

a[i]与b[i]相互看见==他们中间的牛(a[i+1]到b[i-1])身高都比他们矮,于是把他们身高都减去1即可。关于区间修改,维护差分数列

注意坑点,输入数据可能有重复以及可能位置顺序不对。

codes

#include
#include
#include
using namespace std;
const int maxn = 10010;

mapint,int>, bool>existed;
int c[maxn], d[maxn];

int main(){
    int n, p, h, m;
    cin>>n>>p>>h>>m;
    for(int i = 1; i <= m; i++){
        int a, b;  cin>>a>>b;
        if(a > b)swap(a, b);
        if(existed[make_pair(a,b)])continue;
        d[a+1]--;  d[b]++;
        existed[make_pair(a,b)] = 1;
    }
    for(int i = 1; i <= n; i++){
        c[i] = c[i-1]+d[i];
        cout<'\n';
    }
    return 0;
}
点赞

发表评论

昵称和uid可以选填一个,填邮箱必填(留言回复后将会发邮件给你)
tips:输入uid可以快速获得你的昵称和头像