cf edu(round100)-Find The Array

链接：https://codeforces.ml/contest/1463/problem/B

题目大意

给你一个序列a[1..n]，其中$1\leq a_i \leq 10^9$，S为a所有元素的和。要求构造一个”美丽序列“B[1..n]满足：

$1≤b_i≤10^9 $
要么$b_i$ 整除$b_{i+1}$ ，要么$b_{i + 1}$ 整除$b_i$ 。
$2\sum_{i=1}^{n}{|a_i-b_i|}\leq S$

保证一定有解，输出任意一种。

分析

很有意思但是不难的构造题。

因为是第三个条件的左边有个系数2，不难想到利用2进制进行构造。具体做法为，对于任意$a_i$，其对应的$b_i$就是$2^{\lfloor \log_{2}{a_i}\rfloor}$，也就是$a_i$的二进制最高位。

这时我们不难发现，$|a_i-b_i|\leq \frac{a_i}2$，所以一定是满足条件3的。同时，因为B[1..n]都是2的幂，因此任意B的任意两个元素必然有一个可以整除对方。于是这道题就这么做完了~~（又水了一骗博客）~~。

AC代码

#include <bits/stdc++.h>
using namespace std;
const int N = 50 + 5;

int a[N], n;

int getB(int x) {
    for (int i = 0; i <= 31; i++) {
        if ((1 << i) > x) return 1 << (i - 1);
    }
    return 1;
}

int main() {
    int T; cin >> T;
    while (T--) {
        cin >> n;
        for (int i = 0; i < n; i++) {
            scanf("%d", a + i);
            printf("%d ", getB(a[i]));
        }
        printf("\n");
    }
    return 0;
}