题号 NC25044
名称 Tallest Cow
来源 USACO

题目描述

有N头牛站一排 ，只有当两头牛之间的牛的身高都比他们矮是这两头牛才能相互看见，已知n个牛中最高的牛的高度h，以及r组可以相互看见的牛，问这n牛每一头牛最高是多少，并且保证满足这r组牛可以相互看见。

样例

输入
9 3 5 5
1 3
5 3
4 3
3 7
9 8
输出
5
4
5
3
4
4
5
5
5

算法

(差分 + 贪心)

假设r = 0，则最优的情况就是所有牛的身高都为h，假设r = 1，则第i头牛和第j头牛可以相互看看见，则最优的情况就是[i + 1,j - 1]这个区间内的牛的身高，都变成h-1，在r = 1的基础上在添加一个条件，第l头牛和第r头牛可以相互看看见，那么此时的最优解，就是在满足r = 1的条件时n头牛身高最优的情况下，[l + 1,r - 1]这个区间内的牛的身高都减少1，r > 2的情况以此类推。区间统一减去一个数可以用差分。

时间复杂度 O（N）

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
#include <cstdio>

using namespace std;
const int N = 10010;
typedef pair<int,int> PII;
map<PII,bool> H;
int n,p,h,m;
int s[N];

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

    while(m --)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        if(a > b) swap(a,b);
        if(H[make_pair(a,b)]) continue;
        s[a + 1] --,s[b] ++;
        H[make_pair(a,b)] = true;
    }
    for(int i = 1;i <= n;i ++)
    {
        s[i] += s[i - 1];
        printf("%d\n",s[i] + h);
    }
    return 0;
}