Find the Array

链接：https://codeforces.com/problemset/problem/1463/B
题意：给定一个序列，让构造出一组数列，满足两倍的所有差值的绝对值之和满足<=所有数的和，其中每个数都不能超过1e9，并且相邻两个数不能为互相的倍数。
思路：
构造一个为2的等比数列就行了，对于每一位找到不超过它的最大的等比数就可，哎，我之前想过取平均数的做法或者枚举等比因子，其实快想到了，但还是不信。。证明一下 ，假设每个数为k，那么得到的等比数一定>=k/2，所以加起来一定<=sum/2
代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long 
int a[55];
long long res[55];
int Log(int x)
{
    int res=0;
    while(x!=1)
    {
        x/=2;
        res++;
    }
    return res;
}
signed  main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        long long sum=0;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            int t1=Log(a[i]);
            int t2=t1+1;
            //cout<<t1<<" "<<t2<<endl;

            if(abs((1ll<<t2)-a[i])<abs((1ll<<t1)-a[i]) && (1ll<<t2)<1e9)
                cout<<(1ll<<t2)<<" ";
            else
                cout<<(1ll<<t1)<<" ";
        }
        cout<<endl;

    }
    return 0;
}