题目传送门

思路

先来看一下构造要求，核心思路是围绕着第三点要求展开的：

2×∑i=1n∣ai−bi∣≤S2 \times \sum\limits_{i=1}^{n} |a_i-b_i| \leq S

由于 S=∑i=1naiS = \sum\limits_{i=1}^{n} a_{i}，我们可以先不妨设 bi≤aib_i \le a_i 将绝对值展开，得到：对于每一个 ii，都满足 ⌊ai2⌋≤bi≤ai\left \lfloor \frac{a_i}{2} \right \rfloor \le b_i \le a_i，同时通过二进制的性质可以得出，在范围 [⌊ai2⌋,ai]\left [ \left \lfloor \frac{a_i}{2} \right \rfloor , a_i \right ] 当中必然存在一个 2k2^k，因此我们只要让每一个 bib_i 都等于 2k2^k 即可。

那么应该如何找到这个 kk 的大小呢？如果假设 ai=15=(1111)2a_i = 15 = (1111)_2，则 ⌊ai2⌋=7=(111)2\left \lfloor \frac{a_i}{2} \right \rfloor = 7 = (111)_2，可以发现我们只需要保留最高位的 11 就可以得到 bib_i 的值，是不是和树状数组中的 lowbitlowbit 操作很像？。

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
// Problem: Find The Array
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1463B
// Memory Limit: 250 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
// #define int long long

const int N = 1e2 + 9;
const int INF = 0x3f3f3f3f;
int a[N];

int lowbit(int x)    // 熟悉的 lowbit 操作得到最高位的 1
{
    return x & -x;
}

void solve()
{
    int n; cin >> n;
    for (int i = 1; i <= n; i ++) cin >> a[i];
    
    for (int i = 1; i <= n; i++)
    {
        int x = a[i];
        while (x - lowbit(x)) x -= lowbit(x);	// 不断减去次位的 1
        cout << x << " \n"[i == n];				// 输出剩下的 x，i == n 时候自动换行
    }
}

signed main()
{
    // ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T; cin >> T;
    while (T --)
        solve();	
    return 0;
}