H题另一种比较好想的暴力解法

对数组a从小到大排序并去重后，容易证明：将最小数对次小数翻折后整个数组的范围必然会减小。我们设数组a的最小值为x，次小值为y，第三小值为z，即每次操作都让x:=x+2(y-x)，用set维护数组a即满足排序去重。需要注意的是，当x和y都与z差值很大的时候，可计算xy的差值使xy一步翻折很多次接近z，即令A:=(z-x)-(z-x)%(y-x)+x，然后令B:=A+(y-x)。操作到数组中只剩1个或2个数时，答案就是a中最大值减最小值。 以下代码可通过本题：

#include<bits/stdc++.h>
#define int long long
using namespace std;
void solve()
{
	int n;cin>>n;
	set<int> a;
	for(int i=0;i<n;i++)
	{
		int t;cin>>t;
		a.insert(t);
	}
	while(a.size()>2)
	{
		int x=*a.begin();
		a.erase(a.begin());
		int y=*a.begin();
		a.erase(a.begin());
		int z=*a.begin();
		int A=(z-x)-(z-x)%(y-x)+x;
		int B=A+(y-x);
		a.insert(A);
		a.insert(B);
	}
	cout<<(*a.rbegin()-*a.begin())<<endl;
}
signed main()
{
    int testcases = 1;
    cin >> testcases;
    while (testcases--)
        solve();
    return 0;
}