4.17 离散化习题

不理解啊不理解，找一堆和离散化没什么关系，中间最多 sort 一下的题就叫离散化练习题，打着离散化的牌子实则是一堆数据结构，意义何在？不懂啊不懂。

今天只贴一道我比较喜欢的题，也是感觉唯一一道可做题。

ACWing 2014. 岛  传送门

思路非常的简单（但其实还是看了题解....）。考虑枚举怎么淹过去，显然我们尽量要让高一块的突出去，所以如果这一块比前一块高，用差分的思想，对于这两个高度之间的水位高度，它都能产生 1 的贡献。然后统计就可。注意要离散化。

已经爱上用 map 了，map 会直接进行去重。以及 map 的 [] 操作很好用，对于没有离散化的元素可以直接引用。唯一的缺点就是平衡树实现导致略慢，但是非常好写。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5 + 10;
int n;
int a[N];
ll sum, ans;
map<int, int> b;
int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++ )
    {
        scanf("%d", &a[i]);
        if(a[i] > a[i - 1])
        {
            b[a[i - 1]] ++;
            b[a[i]] --;
        }
    }
    for(auto i : b)
    {
        sum += i.second;
        ans = max(ans, sum);
    }
    printf("%d", ans);
    return 0;
} 

一些废话：不能独立写出来正确的数据结构导致我比较的抽象的不会这些练习题。啊。崩溃的。

但是称为排序练习题多少有点......

时间不够，以及自身的懒惰。都是很大的问题。