A16298 | Add, Divide and Floor
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
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.
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.
输入格式
The first line contains a single integer $t$ ( $1 \le t \le 10^4$ ) — the number of testcases.
The first line of each testcase contains a single integer $n$ ( $1 \le n \le 2 \cdot 10^5$ ).
The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ( $0 \le a_i \le 10^9$ ).
The sum of $n$ over all testcases doesn't exceed $2 \cdot 10^5$ .
The first line of each testcase contains a single integer $n$ ( $1 \le n \le 2 \cdot 10^5$ ).
The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ( $0 \le a_i \le 10^9$ ).
The sum of $n$ over all testcases doesn't exceed $2 \cdot 10^5$ .
输出格式
For each testcase, 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 in the next line. If there are multiple answers, print any of them.
If the number of operations is less than or equal to $n$ , then print the chosen $x$ for each operation in the next line. If there are multiple answers, print any of them.
输入输出样例
输入 #1
4 1 10 2 4 6 6 2 1 2 1 2 1 2 0 32
输出 #1
0 2 2 5 1 1 6
In the first testcase, all elements are already equal, so $0$ operations are required. It doesn't matter if you print an empty line afterwards or not.
In the second testcase, you can't make less than $2$ operations. There are multiple answers, let's consider the answer sequence $[2, 5]$ . After applying an operation with $x = 2$ , the array becomes $[\lfloor \frac{4 + 2}{2} \rfloor, \lfloor \frac{6 + 2}{2} \rfloor] = [3, 4]$ . After applying an operation with $x = 5$ after that, the array becomes $[\lfloor \frac{3 + 5}{2} \rfloor, \lfloor \frac{4 + 5}{2} \rfloor] = [4, 4]$ . Both elements are the same, so we are done.
In the last testcase, you can't make less than $6$ operations. Since $6$ is greater than $n$ , you don't have to print them. One possible answer sequence is $[0, 0, 0, 0, 0, 0]$ . We are just dividing the second element by $2$ every time and not changing the first element.
In the second testcase, you can't make less than $2$ operations. There are multiple answers, let's consider the answer sequence $[2, 5]$ . After applying an operation with $x = 2$ , the array becomes $[\lfloor \frac{4 + 2}{2} \rfloor, \lfloor \frac{6 + 2}{2} \rfloor] = [3, 4]$ . After applying an operation with $x = 5$ after that, the array becomes $[\lfloor \frac{3 + 5}{2} \rfloor, \lfloor \frac{4 + 5}{2} \rfloor] = [4, 4]$ . Both elements are the same, so we are done.
In the last testcase, you can't make less than $6$ operations. Since $6$ is greater than $n$ , you don't have to print them. One possible answer sequence is $[0, 0, 0, 0, 0, 0]$ . We are just dividing the second element by $2$ every time and not changing the first element.
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？
提交通过
评测结果：Accepted