一、题目描述

原题链接

给定一个长度为 $n$ 的序列 ${a_n}$。每次操作你需要选择一个整数 $x$ 并将所有 $a_i$ 替换为 $\lfloor \frac {a_i + x}2 \rfloor$。求至少多少次操作后能将所有 $a_i$ 变相同。

若最少次数小于等于 $n$，输出操作次数和每次操作所选择的 $x$。否则仅输出操作次数。

$1 \le n \le 2 \times 10^5$，$0 \le a_i \le 10^9$。

二、解题思路

  通过举几个例子就会发现，实际上选多大的 $x$ 对结果没有产生实质的影响，实际上只需要考虑 $0$ 和 $1$ 即可，又会发现进行操作后数组的元素相对大小并没有发生改变，所以我们可以忽略中间元素，只考虑最大值和最小值即可， 因为我们的目的是为了让两个数相等，怎么样才能让两个数相等？很显然是需要让两个数越来越接近，在题目中因为其中的一个步骤是对元素进行除 $2$，因此只要不断操作最后的值都会等于一个值，我们现在需要做的就是如何通过调整 $x$ 让值快速的变统一。

  我们假设最大值和最小值同为奇数，会发现不管 $x$ 选什么对于答案的贡献都是一样的，若最大值和最小值同为偶数，也是同理，当最小值为偶数，最大值为奇数时，$x = 0$ 贡献更高，最简单的例子则为 $4 \ 5$，当最大值为偶数，最小值为奇数，此时 $x = 1$ 贡献更高（可以简单举个例子，会发现这样计算后两者更加接近）。将几种情况分开执行即可。

  本题的核心是让两个数慢慢接近，所以能达到每一步都慢慢接近的方法才是最好的做法。

三、AC代码

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

void sol()
{
    int n;
    cin >> n;
    ll a[n + 10] = {0};
    ll cnt = 0;
    for (int i = 1; i <= n; i++)
    {
        scanf("%lld", &a[i]);
    }
    sort(a + 1, a + 1 + n);
    vector<ll> ans;
    while (a[1] != a[n])
    {
        if (a[1] % 2 == 1 && a[n] % 2 == 0)
        {
            ans.push_back(1);
            a[1] = (a[1] + 1) / 2;
            a[n] = (a[n] + 1) / 2;
        }
        else
        {
            ans.push_back(0);
            a[1] = a[1] / 2;
            a[n] = a[n] / 2;
        }
    }
    cout << ans.size() << endl;
    if (ans.size() <= n)
    {
        for (auto i : ans)
        {
            cout << i << " ";
        }
        cout << endl;
    }
}

int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        sol();
    }

    system("pause");
    return 0;
}