链接:
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;
}