题目描述

难度分:$1400$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$。

每组数据输入$n(1 \leq n \leq 2 \times 10^5)$和长为$n$的数组$a(0 \leq a[i] \leq 10^9)$。

每次操作，你可以选一个在$[0,10^{18}]$中的整数$x$，然后把每个$a[i]$都更新成 $\lfloor \frac{a[i] + x}{2} \rfloor$。至少操作多少次，可以使所有$a[i]$都相同？

输出最小操作次数。如果操作次数$\leq n$，额外输出每次操作选的$x$。

输入样例

4
1
10
2
4 6
6
2 1 2 1 2 1
2
0 32

输出样例

0
2
2 5
1
1
6

算法

打表找规律

看到$x \in [0,10^{18}]$，且第二个$case$答案是2 5就感觉出题人满满的恶意，让人觉得$x$的取值可以千奇百怪。实际上$x=0$或者$1$就可以，本质上就是每个数是向下取整还是向上取整。

我们可以造一些小$case$，打个表观察一下，发现当最小值是奇数的时候$x=1$，偶数的时候$x=0$。考虑到这个$floor$操作并不会影响数组中元素的相对大小，这样就可以模拟了，不断对最大值和最小值操作，直到最大值和最小值相等，把中间的$x$保存到一个答案数组中。

如果答案数组长度$\leq n$就输出长度和各个元素，否则就只输出长度。

复杂度分析

时间复杂度

整个算法就是整个数组的最大值和最小值不断除以$2$（可能向上取整也可能向下取整），找到最值的时间复杂度是$O(n)$，模拟的时间复杂度是$O(log_2A)$，其中$A$是数组中元素的值域。

空间复杂度

空间消耗的瓶颈在于答案数组，需要存$O(log_2A)$级别的元素个数，因此额外空间复杂度为$O(log_2A)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 200010;
int t, n;
LL a[N];

int main() {
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        LL mn = 1e9, mx = -1;
        for(int i = 1; i <= n; i++) {
            scanf("%lld", &a[i]);
            mn = min(mn, a[i]);
            mx = max(mx, a[i]);
        }
        if(n == 1) {
            puts("0");
        }else {
            vector<int> ans;
            while(mn != mx) {
                int x = mn&1;
                ans.push_back(x);
                mn = (mn + x) >> 1;
                mx = (mx + x) >> 1;
            }
            printf("%d\n", (int)ans.size());
            if(ans.size() <= n) {
                for(int x: ans) {
                    printf("%lld ", x);
                }
            }
            puts("");
        }
    }
    return 0;
}