链接:

https://www.acwing.com/problem/content/103/

题意:

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

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

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

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

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

思路:

维护差分数组,对于a,b,Sub[a+1]-1, Sub[b]+1.即可.表示了a到b之间的值起码要少1.

处理重复,和相邻.

代码:

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e4+10;

map<pair<int, int>, bool> mp;

int Sub[MAXN], Ori[MAXN];

int n, p, h, m;

int main()

{

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

    int a, b;

    for (int i = 1;i <= m;i++)

    {

        scanf("%d%d", &a, &b);

        if (a > b)

            swap(a, b);

        if (a+1 == b)

            continue;

        if (mp[make_pair(a, b)])

            continue;

        mp[make_pair(a, b)] = true;

        Sub[a+1] -= 1;

        Sub[b] += 1;

    }

    Ori[p] = h;

    for (int i = p;i >= 1;i--)

        Ori[i-1] = Ori[i]-Sub[i];

    for (int i = p;i <= n;i++)

        Ori[i+1] = Ori[i]+Sub[i+1];

    for (int i = 1;i <= n;i++)

        printf("%d\n", Ori[i]);

    return 0;

}

巴特西

Acwing-101-最高的牛(差分)

链接:

题意:

思路:

代码:

最新文章

热门文章