AcWing打卡-2014-岛
2014. 岛
题目描述:
每当下雨时，农夫约翰的田地总是被洪水淹没。
由于田地不是完全水平的，所以一些地方充满水后，留下了许多被水隔开的“岛”。
约翰的田地被描述为由 \(N\) 个连续高度值 \(H_1,…,H_N\) 指定的一维场景。
假设该场景被无限高的围墙包围着，请考虑暴雨期间发生的情况：
最低处首先被水覆盖，形成一些不连贯的岛，随着水位的不断上升，这些岛最终都会被覆盖。
一旦水位等于一块田地的高度，那块田地就被认为位于水下。
上图显示了一个示例：在左图中，我们只加入了刚好超过 \(1\) 单位的水，此时剩下 \(4\) 个岛（最大岛屿剩余数量），而在右图中，我们共加入了 \(7\) 单位的水，此时仅剩下 \(2\) 个岛。
请计算，暴风雨期间我们能在某个时间点看到的最大岛屿数量。
水会一直上升到所有田地都在水下。
输入格式
第一行包含整数 \(N\)。
接下来 \(N\) 行，每行包含一个整数表示 \(H_i\)。
输出格式
输出暴风雨期间我们能在某个时间点看到的最大岛屿数量。
数据范围
\(1≤N≤1051≤N≤105,\)
\(1≤Hi≤1091≤Hi≤109\)
输入样例：
输出样例：
tags: 离散化、枚举
这题还是比较难的哈??，一开始想了很久都没有想明白，还是边看y总视频边写出来的。还是太菜了，根本没想到怎么转换。
我们首先要知道，一开始这些小山都是连片的，所以一开始只有1个岛，后面随着海平面上升，分散出了被水分隔的小岛，题目要问的是在这个过程中最大的小岛数量，因为初始时是只有1个小岛，后续所有小山都被 覆盖了，所以没有小岛了，要求的是这个过程中的最大的小岛数量。
在水平面上升的这个过程中，并不是所有的高度都会引起小岛数量的变化，所以我们只考虑变的量，就是当水平面上升到某个高度时，引起了岛的数量的变化的高度。于是所有没有出现过的高度，都不需要考虑，而所有出现过的高度，都需要考虑会不会引起岛的数量的变化。
于是可以继续考虑枚举每一个出现过的高度，当水平面上升到这些高度时，此时的小岛数量，在这些状态中求出小岛的最大数量。于是，求当水平面上升到某一个高度时，对小岛数量变化的影响，一共有4种情况：
- 小山的形状呈现上升趋势，此时虽然较矮的小岛先被淹没，但是不影响小岛的数量，总的来说还是1个小岛，只是小岛的面积变小了，直到把最高的小山淹没了，此时对小岛的数量影响是0，\(h[i+1]\gt h[i]\gt h[i-1]\)
|
| |
| | | ...
i-1 i i+1
- 小山的形状呈现下降的趋势，和第1种情况对称，也是只会影响小岛的面积，但是小岛数量依旧还是\(1\)，此时对小岛的数量影响依旧是0,\(h[i-1]\gt h[i]\gt h[i+1]\)；
|
| |
| | | ...
i-1 i i+1
- 小山的性质呈现凸字形，中间的小山的比左右两边的小山更高，如果淹没了较为矮的两座小山之一，都不会使小岛数量有变化，如果淹没了中间的小山，则会使这一片小岛全都被水淹没，总的小岛数量\(-1\)，\(h[i]>h[i-1]\&\&h[i]>h[i+1]\)；
|
| |
| | |
| | | ...
i-1 i i+1
- 小山的形状呈现凹字形，中间的小山比左右两边的小山都更低，如果淹没了中间的小山，还没有淹没旁边的两座小山时，会使小岛的数量+1，因为从中间分开了一座小岛，从而使小岛数量增加，\(h[i] \lt h[i-1] \&\& h[i] \lt h[i+1]\)；
|
| |
| | |
| | | ...
i-1 i i+1
于是枚举\(n\)次，每次枚举判断是否更新都是\(O(1)\)的时间复杂度，又因为枚举需要从下往上枚举，所以需要排序，排序是\(nlogn\)的复杂度，于是整体的复杂度为\(nlogn\)。
对于一些特殊情况，我们可以将其统一化为上面的4种情况。假如有一连片的相等小山，就需要重复判断，相等的那一片区域不能确定长度，很可能是单次判断的复杂度从\(O(1)\)降到\(O(n)\)。于是考虑，将相邻的相同小山合并为一座小山就可以了。因为要么一块被淹没，要么都不被淹没，所以把所有相邻的小山删除掉。
因为是按照小山的高度从低到高枚举，所以我们需要对小山的高度进行排序。然后我们对所有的小山按照高度排序后，不仅需要知道它的高度，还需要知道小山的左右两边是谁，所以还需要存小山的坐标，可以用\(pair\)来同时存储小山的高度和它的坐标。
同时，还需要注意，一批同一高度的小山，是同一时间被淹没的，只有当同一高度的小山全部被淹没后，才能更新结果，所以需要判断\(q[i].y\)与\(q[i+1].y\)的关系，如果相同高度都判断完成后才可以更新答案。
#include
#include
#include
using namespace std;
typedef pair PII;
#define x first
#define y second
const int N = 1e5 + 10;
int n;
int h[N]; //所有小山的高度
PII q[N];
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &h[i]);
n = unique(h + 1, h + n + 1) - h - 1; // 删除所有相邻元素
for (int i = 1; i <= n; i++)
q[i] = {h[i], i};
sort(q + 1, q + n + 1);
int res = 1, cnt = 1;
for (int i = 1; i <= n; i++)
{
int k = q[i].y; //当前正在被淹没的小山下标
if (h[k - 1] < h[k] && h[k + 1] < h[k])
cnt--;
else if (h[k - 1] > h[k] && h[k + 1] > h[k])
cnt++;
if (q[i].x != q[i + 1].x)
// 因为前面只是判重的相邻元素,此时还需要对不相邻的但相同高度的小山进行同步的更新,因为只能有一次的更新
res = max(res, cnt);
}
printf("%d\n", res);
return 0;
}