题目描述
难度分:$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;
}