最高的牛

最高的牛

有 $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$

输入样例

1
2
3
4
5
6
9 3 5 5
1 3
5 3
4 3
3 7
9 8

输出样例

1
2
3
4
5
6
7
8
9
5
4
5
3
4
4
5
5
5

注意:

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

解析

需要用到知识点 差分数组 (复习)

1
2
3
有数组 A[1] A[2] A[3] A[4]
差分数组 B[i] = A[i] - A[i - 1]
可得 A[i] = B[1] + B[2] + B[3] + .... + B[i]

由问题可得,我们需要始终让数组 $a_n$ 的某区间 $[l,r]$ 中,$a_l$ 与 $a_r$ 的值在这个区间最大。

那很简单,让每次的询问中使 $[l+1,r-1]$ 的区间内所有数 $-1$ 就好,这样就能保证 $a_l$ 与 $a_r$ 在 $[l,r]$ 中最大,且满足我们尽可能让每头牛的身高最高的条件。

这里的区间数作加减,用差分数组完成即可。

最后就是 此题中给出的关系对可能存在重复 的条件,我们只需要排序一下,看看当前的区间是否和上一个区间不同就好。(因为 $1≤N≤10000$,所以没有考虑用二维数组标记 64MB会MLE,但题解里似乎有用 bool 数组进行标记的)

剩下的看代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <cstdio>
#include <iostream>
#include <algorithm>
//前排提醒 更简单的看yxc的代码
int n, p, h, m;

const int N = 10005;
std::pair<int, int> arr[N];
int B[N];

int cmp(std::pair<int, int>a, std::pair<int, int>b) { //用pair排序得构造
if(a.first != b.first) return a.first < b.first;
else return a.second < b.second;
}

int main() {
scanf("%d %d %d %d", &n, &p, &h, &m);
for (int i = 1; i <= m; i++) {
scanf("%d %d", &arr[i].first, &arr[i].second);
if(arr[i].first > arr[i].second) std::swap(arr[i].first, arr[i].second);
} //保证一定是左区间小于右区间

std::sort(arr + 1, arr + 1 + m, cmp);

for (int i = 1; i <= m; i++) { //如果相同就跳过,不同就进行区间操作
if(arr[i].first == arr[i - 1].first && arr[i].second == arr[i - 1].second) continue;
B[arr[i].first + 1] -= 1;
B[arr[i].second] += 1;
}

int ans = h;
for (int i = 1; i <= n; i++) {
ans = ans + B[i];
printf("%d\n", ans);
} return 0;
}

注意注意

我只说明了 $[l + 1,r - 1]$ 上 $-1$ 的方法的最优性,没有证明其正确性

1
2
3
4
5
6
7
8
9
10
11
若存在数据
6 6 5 3
1 4
2 4
3 6
则由方法可得
5 4 3 4 4 5
并不满足 3 6 的询问,但这并不能说明方法的错误,只是因为这种数据不可能得到一个正确解
所以为了保证数据的正确性 若出现询问区间交叉的情况,设不合理的区间为 [l, r]
那么[l, r]一定会再次进行询问,直到原来的两次询问都为合法询问(满足题意要求的正确答案)为止
所以可以得到我们方法一定是正确的

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!