小红的数组清空
时间限制：1秒 空间限制：256M
网页链接
牛客tracker
牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！
题目描述
小红拿到了一个数组，她准备用尽可能少的代价将该数组全部清空。
小红有两种操作：
- 直接删除一个元素x xx，花费代价为1 11。
- 若上一个删除的元素为x xx，那么直接删除一个元素x + 1 x+1x+1，花费代价为0 00。该操作仅当x + 1 x+1x+1在数组中存在时才可进行。
请你求出小红清空整个数组的最小代价。
输入描述：
第一行输入一个正整数n nn，代表数组的大小。
第二行输入n nn个正整数a i a_iai，用空格隔开。代表数组的元素。
1 ≤ n ≤ 10 5 1≤n≤10^51≤n≤105
1 ≤ a i ≤ 10 9 1≤a_i≤10^91≤ai≤109
输出描述：
输出一个正整数，代表小红清空整个数组的最小代价。
示例1
输入：
3 1 2 3输出：
1说明：
第一次操作，删除1 11，代价为1 11。
第二次操作，删除2 22，代价为0 00。
第三次操作，删除3 33，代价为0 00。
示例2
输入：
5 2 1 6 5 7输出：
2示例3
输入：
2 1 1输出：
2解题思路
本题采用排序+双端队列贪心策略求解最小清空代价，核心是最大化零代价删除的连续递增序列次数，先将数组排序以按数值递增顺序处理元素，用双端队列维护可衔接的“前驱数值”；遍历每个元素时，先移除队列中小于当前元素− 1 -1−1的无效前驱（无法衔接），若队列首元素等于当前元素− 1 -1−1，说明可零代价删除该元素（弹出前驱、将当前元素入队作为新前驱），否则需花费1 11代价删除（当前元素入队、答案加1 11）；排序操作时间复杂度为O ( n l o g n ) O( n logn)O(nlogn)，遍历及队列操作整体为O ( n ) O(n)O(n)，完美适配n ≤ 1 e 5 n≤1e5n≤1e5的规模，通过贪心选择最优的前驱衔接，最大化零代价操作次数，精准得到清空整个数组的最小代价。
代码内容
#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefpair<ll,ll>pii;constll p=1e9+7;constll N=1e6+10;intmain(){ll n;cin>>n;vector<ll>a(n+1);for(ll i=1;i<=n;i++)cin>>a[i];sort(a.begin()+1,a.end());deque<ll>q;ll ans=0;for(ll i=1;i<=n;i++){while(!q.empty()&&q.front()<a[i]-1)q.pop_front();if(!q.empty()&&q.front()==a[i]-1){q.pop_front();q.push_back(a[i]);}else{q.push_back(a[i]);ans++;}}cout<<ans<<endl;return0;}
)
