ACM - CF - 1496B - 二分

CF题目链接

题意：
给定一n个数的数组，数组元素不重复，给定k次操作。问：k次操作之后，数组中不重复的元素个数是多少。
操作定义为：(max{} + mex{}) / 2向上取整。
其中：max{}是数组中最大的数，mex{}是数组中第一个未出现的自然数。

样例解释：
4 1
0 1 3 4
1次操作，mex{} = 2, max{} = 4, 添加3，答案是4
3 1
0 1 4

3 0
0 1 4
0次操作，答案是3
3 2
0 1 2
两次操作，mex{}=3, max{}=2, 添加3；mex{}=4,max=3，添加4，答案是5
3 2
1 2 3
两次操作，mex{}=0, max{}=3, 添加2，变成{1 2 2 3}；第二次操作，mex{}=0, max{}=3,变成{1 2 2 2 3},答案是3

两个点：
（1）mex{}怎么计算，即找第一个未出现的自然数
数组排序。若a[i] = i，说明在i之前都是有序的，且都出现了。即二分

（2）题目的k次，骗人的。重点是不同的数。
观察后两个样例。
第一个，由于出现了 0 ~ n-1，根据规则，mex{}=n, max{}=n-1, 会添加n；所以第二次添加n+1，以此类推
第二个，由于2是重复出现的，所以之后都不用再算。k那么大，一直算，会超时的
这两个即为边界条件

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 20;
int T,n,k;
int a[maxn];

int main(){
    //freopen("input.txt", "r", stdin);
    scanf("%d",&T);
    while(T--){
        memset(a, 0, sizeof(a));
        scanf("%d%d", &n, &k);
        for(int i = 0; i < n; i++)
            scanf("%d", &a[i]);
        sort(a, a+n);

        if (a[n - 1] == n - 1){
            printf("%d\n", n + k);
            continue;
        }
        int l, r, mid, maxx = a[n - 1], tmp;
        //printf("%d\n", maxx);
        int num;
        for(num = 1; num <= k; num++){
            //printf("num = %d\n", num);
            l = 0;
            r = n - 1 + num - 1;
            while(l <= r){
                mid = (l + r) >> 1;
                //printf("%d %d\n", mid, a[mid]);
                if (a[mid] == mid)
                    l = mid + 1;
                else
                    r = mid - 1;
            }
            //printf("%d\n", l);
            tmp = (l + maxx + 1) / 2;
            //printf("tmp = %d maxx = %d\n", tmp, maxx);

            l = 0;
            r = n - 1 + num - 1;
            while(l <= r){
                mid = (l + r) >> 1;
                if (a[mid] <= tmp)
                    l = mid + 1;
                else
                    r = mid - 1;
            }

            //printf("l,r,mid = %d %d %d %d %d %d\n", l, a[l], r, a[r], mid, a[mid]);

            for(int i = n - 1 + num - 1; i >= l ; i--)
                a[i + 1] = a[i];
            a[l] = tmp;
            if (l > 0 && a[l - 1] == tmp) break;
            if (a[l + 1] == tmp) break;

            //sort(a, a + n + num);
            //for(int i = 0; i < n + num; i++)
            //    printf("%d%c", a[i], i == n + num - 1 ? '\n' : ' ');
        }
        int cnt = 1;
        for(int i = 1; i < n + num; i++)
            if (a[i] != a[i - 1] && a[i])
                cnt++;
        printf("%d\n", cnt);
        //for(int i = 0; i < n + num; i++)
        //    printf("%d%c", a[i], i == n + num - 1 ? '\n' : ' ');
    }
    return 0;
}