题目

小明喜欢武侠小说，在武侠世界里，他不但练就了一箭双雕的能力，还可以一箭多雕。
现在所有雕在一条直线上从左到右排列，但是他们的高度不同。而小明想要把他们都射下来。小明使用的是一种特殊的弓箭，他可以将弓箭射到任意一个高度为H的雕，当射中一个高度为H的雕后，弓箭的高度会下降到H-1，再从左到右飞行，直到射到高度为H-1的大雕，再降低1的高度，直到飞出大雕的队列。
由于弓箭数量有限，小明想要知道，最少用多少的弓箭，就可以射下所有的大雕。

输入
第一行一个整数，n表示直线上的大雕数量。
第二行n个整数，表示从左到右每个大雕的高度。

输出
输出一个整数，表示最少用的弓箭数量。

样例

【样例1】

输入

5
2 1 5 4 3

输出

2

【样例2】

输入

5
1 2 3 4 5

输出

5

【样例3】

输入

5
4 5 2 1 4

输出

3

解析

这道题一开始我想复杂了，但实际上问题很简单。可以用一个map来解决，每次输入高度h的时候，如果有高度h+1的大雕，减一个。这样对map的values求和就是答案了。

#include<iostream>
#include<cstdio>
#include<unordered_map>

using namespace std;

int n;
unordered_map<int, int> map;

int main() {
    ios_base::sync_with_stdio(false);
    cin >> n;

    for (int i = 1; i <= n; ++i) {
        int x;
        cin >> x;
        if (map[x + 1] > 0) map[x + 1] -= 1;
        map[x] += 1;
    }

    int ans = 0;
    for (auto e:map) {
        ans += e.second;
    }

    cout << ans;

    return 0;
}