链接:

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
using namespace std;
const int MAXN = 1e4+10;
map, 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;
}