Tallest Cow(POJ3263)-白红宇

Tallest Cow(POJ3263)

阅读量：6914 次

发布时间：2019-06-27

本文共 926 字，大约阅读时间需要 3 分钟。

Tallest Cow(POJ3263)

给出N头牛的身高，和M对关系（ai与bi可以相互看见。即他们中间的牛都比他们矮）。已知最高的牛为第P头，身高为H。求每头牛的身高最大可能是多少。( \(1 \leq N,M \leq 10^4, 1 \leq H \leq 10^6\) )

输入样例：

9 3 5 5

1 3

5 3

4 3

3 7

9 8

输出样例：

分析：

朴素解法：数组C初始化0 ，ai与bi之间的数减一最后设C[P] = 0 即Hi = H+C[i] \(O(NM)\)

前缀和：把对一个区间的操作转化为左右两个端点的操作，再通过前缀和得到原问题的解

数组D初始化0，D[ai+1]-=1,D[bi]+=1 最后 \(C[i] = \sum_{j=1}^iD[j]\) \(O(N+M)\)

题解：

#include
    
     #include
     using namespace std;map
      
       
        ,bool> existed;  //处理重复的成对关系int c[10010],d[10010];int main(){    int n,p,h,m;    cin>>n>>p>>h>>m;        for(int i=1;i<=m;i++){        int a,b,t;        cin>>a>>b;        if(a>b){t=a;a=b;b=t;}        if(existed[make_pair(a,b)])continue;        d[a+1]--;d[b]++;        existed[make_pair(a,b)] = true;    }    for(int i=1;i<=n;i++){        c[i] = c[i-1] + d[i];        cout<
        
         <