Add, Divide and Floor
题目链接:https://codeforces.com/problemset/problem/1901/C
题目描述
You are given an integer array $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$). In one operation, you can choose an integer $x$ ($0 \le x \le 10^{18}$) and replace $a_i$ with $\lfloor \frac{a_i + x}{2} \rfloor$ ($\lfloor y \rfloor$ denotes rounding $y$ down to the nearest integer) for all $i$ from $1$ to $n$. Pay attention to the fact that all elements of the array are affected on each operation.
Print the smallest number of operations required to make all elements of the array equal.
If the number of operations is less than or equal to $n$, then print the chosen $x$ for each operation. If there are multiple answers, print any of them.
题意翻译
给你一个整数数组 $a_1, a_2, \dots, a_n$ ( $0 \le a_i \le 10^9$ )。在一次运算中,你可以选择一个整数 $x$ ( $0 \le x \le 10^{18}$ ),并用 $\lfloor \frac{a_i + x}{2} \rfloor$ 替换 $a_i$ ( $\lfloor y \rfloor$ 表示将 $y$ 舍入为最接近的整数)从 $1$ 到 $n$ 的所有 $i$ 。请注意,每次操作都会影响数组中的所有元素。
打印使数组中所有元素相等所需的最小操作数。
如果操作次数小于或等于 $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对整个数组操作一遍, 这算一次.
现在先考虑x是怎么来的
每次都会+x整除2。
每次加最小值, 那么对数组进行循环,并判断是否每个数都等于最小值。
优化
实际上,只需要对最大值进行操作并判断,判断操作后的最大值是否等于最小值就好了,不需要再加上循环。
python 代码
import sys
input = lambda:sys.stdin.readline().strip()
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
cnt = 0
a.sort()
while a[0] != a[-1]:
a[-1] = (a[-1] + a[0]) // 2
cnt += 1
print(cnt)
if cnt <= n:
print(*[a[0]] * cnt)