• 周二. 8月 9th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

AcWing 101. 最高的牛(差分)

admin

11月 28, 2021

题目

有 N 头牛站成一行,被编队为 1、2、3…N,每头牛的身高都为整数。
当且仅当两头牛中间的牛身高都比它们矮时,两头牛方可看到对方。
现在,我们只知道其中最高的牛是第 P 头,它的身高是 H ,剩余牛的身高未知。
但是,我们还知道这群牛之中存在着 M 对关系,每对关系都指明了某两头牛 A 和 B 可以相互看见。
求每头牛的身高的最大可能值是多少。

输入输出

输入:第一行输入整数 N,P,H,M,数据用空格隔开。
接下来 M 行,每行输出两个整数 A 和 B ,代表牛 A 和牛 B 可以相互看见,数据用空格隔开。
此题中给出的关系对可能存在重复
输出:一共输出 N 行数据,每行输出一个整数。
第 i 行输出的整数代表第 i 头牛可能的最大身高。

思路

n头牛的身高先初始化为最高牛的身高,n头牛一开始都一样高。
假设a、b两头牛可以相互看到,说明a、b中间的都比它们矮,a、b中间的身高-1。可以证明能相互看到的区间不会重合。
在某一段区间加上一个数是差分的应用。height[N]是差分数组。
为了让所有牛的身高都为h,height[0]初始化为h,其他都为0,用前缀和将height相加就能得到所有牛的身高。
当a、b可以下相互看到,height[a+1]–并且height[b]++,会得到a和b之间的牛身高都-1。
注:题目中的关系对可能会重复,重复的关系不需要重复减一,因为需要STL容器set进行去重。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <set>

using namespace std;

const int N = 100010;
int height[N];

int main()
{
    int n,p,h,m;
    cin >> n >> p >> h >> m;
    set<pair<int,int>>existed;  //取出重复的关系
    height[0] = h;
    for (int i = 0; i < m; i ++ ){
        int a,b;
        cin >> a >> b;
        if(a > b) swap(a,b);    //调整a、b大小关系
        if(!existed.count({a,b})){
            existed.insert({a,b});
            height[a+1]--;height[b]++;
        }
    }
    for (int i = 1; i <= n; i ++ ){
        height[i] += height[i-1];
        cout << height[i] << endl;
    }
}
作者:inss!w!
版权声明:本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!

发表评论

您的电子邮箱地址不会被公开。