问题 M: 一箭多雕

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

输入

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

输出

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

样例输入 Copy

【样例1】
5
2 1 5 4 3
【样例2】
5
1 2 3 4 5
【样例3】
5
4 5 2 1 4

样例输出 Copy

【样例1】
2
【样例2】
5
【样例3】
3

提示

样例1解释
第一箭射向第一个大雕，射中后高度下降到1,会射中第二只大雕。
第二箭射向第三个大雕，依次射中高度为5,4,3的三只大雕。
样例2解释
5只大雕，分别使用1个弓箭。
样例3解释
第一箭射向第一个大雕，射中后高度下降到3。
第二箭射向第二个大雕，射下高度为5和4的大雕。
第三箭射向第三个大雕，射下高度为2和1的大雕。

【数据范围】
30%的数据，n<=5000, 大雕的高度<=10000
70%的数据，n<=1000000, 大雕的高度<=1000000
100%的数据，n<=1000000, 大雕的高度<=1000000000。

 

 

 

啊，这个竟然能用map解决，我靠我是傻逼

这个思路很简单

int main(){
    int n;
    read(n);
    int ans=0;
    int x;
    for(int i=1;i<=n;i++){
        read(x);
        if(mp[x+1]){
            mp[x+1]--;
        }
        else{
            ans++;
        }
        if(!mp.count(x)){
            mp[x]=1;
        }
        else{
            mp[x]++;
        }
    }
    cout<<ans<<"
";
}