C. Add, Divide and Floor
2huk
·
·
题解
Description
给定一个长度为 n 的序列 \{a_n\}。每次操作你需要选择一个整数 x 并将所有 a_i 替换为 \lfloor \frac {a_i + x}2 \rfloor。求至少多少次操作后能将所有 a_i 变相同。
若最少次数小于等于 n，输出操作次数和每次操作所选择的 x。否则仅输出操作次数。
## Solution
可以观察到，每次操作后，数字的**相对**大小关系不会发生改变。
例如 $a = \{4, 2, 5\}$，$x = 3$，那么操作后的 $a' = \{3, 2, 4\}$。可以发现 $a_3$ 和 $a'_3$ 分别都是两个序列的最大值，$a_2$ 和 $a'_2$ 都是两个序列的最小值。
那么就启发我们不用同时维护原序列中的所有值，只需要维护序列中的最大值和最小值。当这两个值相等时，就代表序列中所有的数都相同了。
那么问题就被转化成了这样：
> 给定两个整数 $a, b$。每次操作你需要选择一个整数 $x$ 并将 $a \gets \lfloor \frac {a + x}2 \rfloor$，$b \gets \lfloor \frac {b + x}2 \rfloor$。求至少多少次操作后 $a = b$。
每次操作我们肯定是希望利用下取整这个优秀性质来让 $a$ 尽量接近 $b$，也就是想让操作后 $a - b$ 尽量小。那么我们可以直接分讨：
- $a$ 为偶数，$b$ 为偶数：[$x$ 任意取值](https://www.luogu.com.cn/paste/gx9nzxic)；
- $a$ 为奇数，$b$ 为奇数：[$x$ 任意取值](https://www.luogu.com.cn/paste/yvohb091)；
- $a$ 为偶数，$b$ 为奇数：[$x$ 任意一个奇数](https://www.luogu.com.cn/paste/wa8gp7br)；
- $a$ 为奇数，$b$ 为偶数：[$x$ 任意一个偶数](https://www.luogu.com.cn/paste/uaevgx1b)。
然后就解决了。用 `vector` 记录答案即可。
## Code
```cpp
void solve()
{
cin >> n;
a = 0, b = 2e9;
for (int i = 1; i <= n; ++ i )
{
cin >> x;
a = max(a, x);
b = min(b, x);
}
vector<int> res;
while (a != b)
{
if (a % 2 == 0 && b % 2 == 0) x = rand();
else if (a % 2 == 1 && b % 2 == 1) x = rand();
else if (a % 2 == 0 && b % 2 == 1) x = rand() * 2 + 1;
else x = rand() * 2;
a = (a + x) / 2;
b = (b + x) / 2;
res.push_back(x);
}
cout << res.size() << '\n';
if (res.size() <= n)
{
for (auto i : res) cout << i << ' ';
if (res.size()) puts("");
}
return;
}
```