【USACO OPEN12铜组】岛屿
题目描述
每当下雨时，农夫约翰的田地总是被洪水淹没。
由于田地不是完全水平的，所以一些地方充满水后，留下了许多被水隔开的“岛”。
约翰的田地被描述为由 N� 个连续高度值 H1,…,HN�1,…,�� 指定的一维场景。
假设该场景被无限高的围墙包围着，请考虑暴雨期间发生的情况：
最低处首先被水覆盖，形成一些不连贯的岛，随着水位的不断上升，这些岛最终都会被覆盖。
一旦水位等于一块田地的高度，那块田地就被认为位于水下。
上图显示了一个示例：在左图中，我们只加入了刚好超过 11 单位的水，此时剩下 44 个岛（最大岛屿剩余数量），而在右图中，我们共加入了 77 单位的水，此时仅剩下 22 个岛。
请计算，暴风雨期间我们能在某个时间点看到的最大岛屿数量。
水会一直上升到所有田地都在水下。
输入格式
第一行包含整数 N�。
接下来 N� 行，每行包含一个整数表示 Hi��。
输出格式
输出暴风雨期间我们能在某个时间点看到的最大岛屿数量。
数据范围
1≤N≤1051≤�≤105,
1≤Hi≤1091≤��≤109
输入样例：
8
3
5
2
3
1
4
2
3
输出样例：
4
思路
在网上看到了一个大佬的差分做法。
如果 \(a_i >a_{i - 1}\)
那么当水上升到 \(a_{i- 1}\) 时肯定可以多出一块岛屿，但是当水上升到 \(a_i\) 时就不存在了
具体实现看代码
code
#include <bits/stdc++.h>
#define fu(x , y , z) for(int x = y ; x <= z ; x ++)
using namespace std;
const int N = 1e5 + 5;
int n , ans , a[N];
map<int , int> b;
int main () {
scanf ("%d" , &n);
fu (i , 1 , n) {
scanf ("%d" , &a[i]);
if (a[i] > a[i - 1]) b[a[i - 1]] ++ , b[a[i]] --;
}
int sum = 0 , ans = 0;
for(auto ed : b) {
sum += ed.second;
ans = max (ans , sum);
}
printf ("%d" , ans);
return 0;
}