本题解与Luogu同步

Solution

考虑，若出现过就\(+1\)，便是最优答案。

因为右边\(+1\)并不会影响左边

记得多组数据归零变量！

Code

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

int a[100007];
bool vis[200007];
int t, n, ans;

int main()
{
    scanf("%d", &t);
    while(t--)
    {
        ans = 0;
        scanf("%d", &n);
        memset(a, 0, sizeof(a));
        memset(vis, 0 ,sizeof(vis));
        for(int i = 1; i <= n; i++)
        {
            scanf("%d", &a[i]);
            if(vis[a[i]] == false)
            {
                vis[a[i]] = true;
                ans++;
            }
            else
            {
                if(vis[a[i] + 1] == false)
                {
                    vis[a[i] + 1] = true;
                    ans++;
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}