Acwing2014.岛
$Analysis:$
即一条扫描线从下往上扫,求扫描过程中岛屿数量的最大值
$Method1:$ 将高度和顺序建立映射,对高度排序,从小到大枚举高度,讨论所在顺序左右两侧岛的情况
- 如果当前淹没的田左右两侧的田都比自己高,那么就形成了新的岛
- 如果当前淹没的田左右两侧的田都比它矮,那么就减少了一个岛
- 如果只有一侧的田已经淹没,另一侧的田没被淹没,岛的数量就不会变
Ps: 如果存在连续高度相等高度的田,那么不能在要在最后一个相同高度的田淹了之后才判断能是否形成了新的两个岛
即: 对于连续高度的田要将他们看成一个整体的田来判断左右两侧的田
#include<bits/stdc++.h>
using namespace std;
using PII = pair<int, int>;
const int N = 1e5 + 10;
PII a[N];
int rain[N];
int main()
{
int n; cin >> n;
for (int i = 1; i <= n; i ++) cin >> a[i].first, a[i].second = i;
sort(a + 1, a + n + 1);
int ans = 1, cnt = 1;
for (int i = 1; i <= n; i ++)
{
int x = a[i].second;
rain[x] = 1;
bool l = (x > 1) && (!rain[x - 1]);
bool r = (x < n) && (!rain[x + 1]);
if (l && r) ++ cnt;
if (!l && !r) --cnt;
if (a[i + 1].first > a[i].first) ans = max(ans, cnt);
}
cout << ans << endl;
return 0;
}
$Method2:$ 差分思想,将一段连续的上升山峰的效果都归结到最低的一个山峰上面
如下图,只要$a[i]>a[i-1]$,就给$a[i-1]$对应的高度山峰$+1$,$a[i]$对应的山峰$-1,这样扫描线从下往上扫描的过程中,扫到$a[i-1]$就会计数一个山峰,扫到a[i]就会使这次计数归0,只需要从小到大枚举山峰高度求岛屿的前缀和即可,如下右图。
一个山峰只需要记录连续上升的段,因为一个山峰只有一个连续上升的段,即不用管连续下降的段。
$map$会自动按照$first$的值排序,用$for$和$auto$配合遍历是从小到大的
#include<bits/stdc++.h>
typedef long long LL;
using namespace std;
const int N = 100005,M = 1e9+1;
int a[N];
map<int ,int >b;
int n;
int main()
{
cin >> n;
for (int i = 1; i <= n; i ++ ){
cin >> a[i];
if(a[i]>a[i-1]) b[a[i-1]]++,b[a[i]]--; // 数的大小在[a[i-1],a[i]-1]之间的所有数大小都+1
}
LL sum = 0 ,res = 0;
for (auto i:b ){ // 从小到大枚举山峰高度求岛屿前缀和
sum+=i.second;
res = max(res,sum);
}
cout << res;
}
$Summary:$
方法1和方法2其实都是先离散化,再从小到大枚举山峰(田)高度,但方法1是对相同高度的山峰(田)一个一个枚举,方法2是将所有相同高度的山峰(田)的高度和数量建立映射关系,然后利用差分思想将连续上升的一段山峰差分处理,最后求前缀和。