101. 最高的牛(差分)

101. 最高的牛(差分)

先给点我们一个最高牛的高度和不同牛的关系,求所有牛的最大身高

如果给定两头牛的关系,说明两头牛中间所有牛都是比他们矮的,要求最大高度,就只要让中间所有牛高度-1,表示中间所有牛都比他们矮,但是每天牛遍历一遍太慢了,所以使用差分数组优化 

101. 最高的牛(差分)

 有三个问题,如下

1.怎么求差分数组

如图,给定了1,5之间相互看得见,说明中间所有牛高度都要-1,就让b[2]--,b[5]++

如图,假如在1,6互相看得见之前,1,4彼此也看得见,这个意思就是说[2,3]所有牛都比1,4矮,同时[2,5]所有牛也都比1,6矮,那么修改后的差分数组应该如图所示

101. 最高的牛(差分)

 在前缀和处理完差分数组后,就能发现满足[2,3]比1矮2m,[4,5]比1矮1m

2.我们已经算出了差分数组和已知最高牛高度,如何求所有牛高度

由于差分数组前缀和处理后表示的是第i头牛和最高牛的身高差值

原因:差分数组每次修改后,意义是a,b之间所有高度都-1。

假如最高牛高度为5,a为4,由于a到b所有牛都比他们矮,那么经过前缀和处理(a,b)高度都为3

101. 最高的牛(差分)

 

如果一个差分数组前缀和后的数组值为0,说明他不是某个ab之间中间元素,题目没有给明,由于要求所有牛的最大高度,我们默认他是最高牛的高度。

如果一个差分数组前缀和后的数组值<0,说明他是某个ab之间中间元素,比ab都矮,他的高度就是h+数组值

 3.怎么防止有多组相同数据呢

可以用bool数组,存储他们是否之前记录过

bool is_exited[N][N];

或者运用集合set,map

代码

#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int b[N];
set<pair<int, int>> s;
int main()
{
    int n, p, h, m;
    cin >> n >> p >> h >> m;
    for (int i = 0;i < m;i++)
    {
        int x, y;
        cin >> x >> y;
        //x,y之间所有牛的高度-1
        
        if (x > y) swap(x, y);
        if (s.count({ x,y }))
            continue;
        s.insert({x,y});
         b[x + 1]--;
         b[y]++;
    }
    for (int i = 1;i <= n;i++)
    {
        b[i] += b[i - 1];
        cout << b[i]+h << '\n';//最后加上h就可以了
    }
}

上一篇:LeetCode:101. 对称二叉树————简单


下一篇:验证 NAT 配置并进行故障排除