NSOqwq

题解 CF1466B 【Last minute enhancements】

题目大意

给你一个数组。现在,你可以将任意几个元素的值加上 $1$,求出加完以后数组中不同元素的个数最多是多少。

思路

这道题我使用来做。

样例3举例。

先把这个数组塞进桶 ( bucket )里面,然后从最小的元素的值开始遍历。

初始

for (int i = min; i <= max; i += 1)

$i=1$

如果桶里面有多个 i,那么就可以将其中的一个元素加上一,使得数组中不同元素的个数更多。代码表示为:

if (bucket[i] > 1) {
  book[i + 1] = true; // 可以将其中的一个元素加上一,使得数组中不同元素的个数更多
}


$i=3$

如果桶里面只有一个 i,除非之前到达过它,就不能再往上加一了,加了也对不同元素种数没贡献。

如果之前到达过它,那么可以往上加一。

if (bucket[i] == 1) {
  if (book[i]) { // 如果之前到达过它,那么可以往上加一
    book[i + 1] = true;
  }
}


$i=4$

同 $i=2$。


$i=5$

同 $i=3$。

此时 数组中有不止一个 $4$ ,其中一定可以有一个 $4$ 能变成 $5$,所以不用担心 $5$ 能否达到了,将原来数组中的 $5$ 加上 $1$ 以达到6。

到此为止,遍历完了,我们发现 book[1~6] 都是 $1$,说明 $1$ 到 $6$ 都可以达到。输出 $6$。


代码

#include <cstdio>
#include <cstring>
#include <iostream>
int bucket[200005];
bool book[200005];
int t;
int main() {
    scanf("%d", &t);
    while (t--) {
        memset(bucket, 0, sizeof(bucket));
        memset(book, 0, sizeof(book));
        int n;
        scanf("%d", &n);
        int max = 0, min = 2000005;
        for (int i = 1; i <= n; i += 1) {
            int x;
            scanf("%d", &x);
            bucket[x] += 1;
            min = std::min(min, x);
            max = std::max(max, x);
        }
        int cnt = 0; // 这里比之前在“思路”部分讲的内容多了一个动态计数器cnt,这样就不用在最后再遍历一遍book了
        for (int i = min; i <= max; i += 1) { // 遍历
            if (bucket[i] == 1) {
                if (book[i]) {
                    cnt += 1;
                    book[i + 1] = true;
                } else {
                    cnt += 1;
                }
            }
            if (bucket[i] > 1) {
                if (!book[i]) {
                    cnt += 1;
                }
                book[i + 1] = true;
                cnt += 1;
            }
        }
        printf("%d\n", cnt);
    }
  return 0;
}
// qwq

2021-01-01 19:13:31 in 题解