CF1466B Last minute enhancements

传送门

题目大意

给出序列 $x_i$ 单调递增。你可以执行若干次操作(可以不操作)，每次你可以选择一个位置 $1≤i≤n$，并将 $x_i$ 加 1。每个位置最多只能操作一次，你需要通过一些操作，使得最后的 $x$ 序列去重后剩余的元素最多

---

思路1：顺着遍历

这道题给的序列很特殊，是一个单调递增序列，我们很容易想到维护一个数组，边存边计数，并判断是否出现过，如果出现过那就 +1，在判断是否出现过

---

思路2：逆着遍历

我们也可以直接从后往前遍历，因为最大的数 +1 一定也是最优的

单调递增的序列倒着遍历就是单调递减序列，边存边计数也是可以过的

注意: 1, 1, 2, 2 有连续重复的数的情况

---

代码

思路1实现：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
int t,n,ans=0;
bool a_a[200001];
int n_n;//记录每个读入的数 
int main(){
    cin>>t;
    while(t--){
        scanf("%d",&n);
        ans=0;//多测清空！！！ 
        memset(a_a,0,sizeof a_a);//多测清空 
        for(int i=1;i<=n;i++){
            scanf("%d",&n_n);
            if(!a_a[n_n]){//判断原数是否存在 
                a_a[n_n]=1;ans++;
            }
            else if(!a_a[n_n+1]){//判断原数+1是否存在 
                a_a[n_n+1]=1;ans++;
            }
        }
        cout<<ans<<endl;
    }
    return 0; 
}

思路2实现：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
int t,n,a_a[100001];
int ans,last;//last 上一个数的大小 
bool b;//判断是否已经出现过相同的数字并算过 
int main(){
  cin>>t;
  while(t--){
    b=0;
    scanf("%d",&n);
    memset(a_a,0,sizeof a_a);
    for(int i=1;i<=n;i++)scanf("%d",&a_a[i]);
    last=++a_a[n];//最大的数+1 
    ans=1;
    for(int i=n-1;i>=1;i--){//单调递减 
      if(a_a[i]<last&&(a_a[i]+1)!=last){//判断是否符合要求 
      // (a_a[i]+1)!=last : 处理3,3,4,4的情况 
        ans++;b=0;//更新相同的数字是否可加入及时一个+1，一个原数 
        a_a[i]++;
        last=a_a[i];
      }else if(!b||a_a[i]+1==last){//判断是否加过原数 
        b=1;ans++;
        last=a_a[i];
      }
    }
    cout<<ans<<endl;
  }
  return 0;
}