2014. 島
題目描述:
每當下雨時，農夫約翰的田地總是被洪水淹沒，
由于田地不是完全水平的，所以一些地方充滿水后，留下了許多被水隔開的“島”，
約翰的田地被描述為由 \(N\) 個連續高度值 \(H_1,…,H_N\) 指定的一維場景，
假設該場景被無限高的圍墻包圍著，請考慮暴雨期間發生的情況：
最低處首先被水覆寫，形成一些不連貫的島，隨著水位的不斷上升，這些島最終都會被覆寫，
一旦水位等于一塊田地的高度，那塊田地就被認為位于水下，
上圖顯示了一個示例：在左圖中，我們只加入了剛好超過 \(1\) 單位的水，此時剩下 \(4\) 個島（最大島嶼剩余數量），而在右圖中，我們共加入了 \(7\) 單位的水，此時僅剩下 \(2\) 個島，
請計算，暴風雨期間我們能在某個時間點看到的最大島嶼數量，
水會一直上升到所有田地都在水下，
輸入格式
第一行包含整數 \(N\)，
接下來 \(N\) 行，每行包含一個整數表示 \(H_i\)，
輸出格式
輸出暴風雨期間我們能在某個時間點看到的最大島嶼數量，
資料范圍
\(1≤N≤1051≤N≤105,\)
\(1≤Hi≤1091≤Hi≤109\)
輸入樣例：
8
3
5
2
3
1
4
2
3
輸出樣例：
4
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 <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef pair<int, int> 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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/412969.html
標籤：其他
上一篇：演算法競賽——樹和圖的存盤與遍歷