AcWing-101-最高的牛

问题

有 N 头牛站成一行，被编队为1、2、3…N，每头牛的身高都为整数。

当且仅当两头牛中间的牛身高都比它们矮时，两头牛方可看到对方。

现在，我们只知道其中最高的牛是第 P 头，它的身高是 H ，剩余牛的身高未知。

但是，我们还知道这群牛之中存在着 M 对关系，每对关系都指明了某两头牛 A 和 B 可以相互看见。

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

输入格式

第一行输入整数N, P, H, M，数据用空格隔开。

接下来M行，每行输出两个整数 A 和 B ，代表牛 A 和牛 B 可以相互看见，数据用空格隔开。

输出格式

一共输出 N 行数据，每行输出一个整数。

第 i 行输出的整数代表第 i 头牛可能的最大身高。

数据范围

1≤N≤10000,
1≤H≤1000000,
1≤A,B≤10000,
0≤M≤10000

输入样例：

9 3 5 5
1 3
5 3
4 3
3 7
9 8

输出样例：

5
4
5
3
4
4
5
5
5

注意：

• 此题中给出的关系对可能存在重复

思路

由题，可知任意两组配对的牛都不存在交叉的情况，即为任意两组配对[a1,b1]，[a2,b2]不存在交集。

思路一

朴素算法。将读取到的配对升序存入一个map<int,priority_queue<int>>中，第一个泛型指的是左端点，第二个为左端点对应的右端点的优先队列（top为当前队列中的最大值）。再依次遍历每个左端点的右端点队列，从其最右边的右端点开始，左端点和右端点中间的所有元素（不包含两端点）的值设为当前两端点中最小值-1。即可得到结果。

思路二

差分。设置一个height的差分数组，表示牛的高度的差分序列。设height[1]=H（第一条牛的初值），每读取一个匹配对(i,j)，将其中间的（不包含两端点）奶牛的高度都减一，则其差分序列的第i+1位会减一，而第j位会加一，(i+1,j)区间的值不变。配对完后，将差分序列还原为奶牛的高度即可。

题解

题解一

#include<iostream>
#include<cstdio>
#include<map>
#include<queue>

using namespace std;

const int MAX = 10010;

int main() {
    int N, P, H, M;
    int a[MAX];
    map<int, priority_queue<int>> m;

    cin >> N >> P >> H >> M;
    int x, y;
    for (int i = 0; i < M; ++i) {
        scanf("%d%d", &x, &y);
        if (x == y) continue;
        if (x > y) {
            int t = x;
            x = y;
            y = t;
        }

        if (m.find(x) == m.end()) {
            priority_queue<int> q;
            q.push(y);
            m.insert(make_pair(x, q));
        } else m[x].push(y);
    }

    for (int i = 1; i <= N; ++i) {
        a[i] = H;
    }

    for (auto item : m) {
        int l = item.first;
        auto s = item.second;

        while (!s.empty()) {
            int r = s.top();
            s.pop();
            int val = min(a[l], a[r]) - 1;
            for (int i = l + 1; i <= r - 1; i++) {
                a[i] = val;
            }
        }
    }

    for (int i = 1; i <= N; ++i) {
        cout << a[i] << endl;
    }

    return 0;
}

题解二

#include<iostream>
#include<cstdio>
#include<set>

using namespace std;

const int MAX = 10010;
int height[MAX];

int main() {
    int n, p, h, m;
    cin >> n >> p >> h >> m;
    set<pair<int, int>> s;

    height[1] = h;
    int a, b;
    for (int i = 0; i < m; ++i) {
        scanf("%d%d", &a, &b);
        if (a > b) swap(a, b);
        if (!s.count({a, b})) { //不存在
            s.insert({a, b});
            height[a + 1]--;
            height[b]++;
        }
    }

    for (int i = 1; i <= n; i++) {
        height[i] += height[i - 1];
        cout << height[i] << endl;
    }

    return 0;
}