Codeforces 1463 B. Find The Array

本文主要是介绍Codeforces 1463 B. Find The Array，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

You are given an array [𝑎1,𝑎2,…,𝑎𝑛] such that 1≤𝑎𝑖≤109. Let 𝑆 be the sum of all elements of the array 𝑎.

Let’s call an array 𝑏 of 𝑛 integers beautiful if:

1≤𝑏𝑖≤109 for each 𝑖 from 1 to 𝑛;
for every pair of adjacent integers from the array (𝑏𝑖,𝑏𝑖+1), either 𝑏𝑖 divides 𝑏𝑖+1, or 𝑏𝑖+1 divides 𝑏𝑖 (or both);
2∑𝑖=1𝑛|𝑎𝑖−𝑏𝑖|≤𝑆.
Your task is to find any beautiful array. It can be shown that at least one beautiful array always exists.

Input
The first line contains one integer 𝑡 (1≤𝑡≤1000) — the number of test cases.

Each test case consists of two lines. The first line contains one integer 𝑛 (2≤𝑛≤50).

The second line contains 𝑛 integers 𝑎1,𝑎2,…,𝑎𝑛 (1≤𝑎𝑖≤109).

Output
For each test case, print the beautiful array 𝑏1,𝑏2,…,𝑏𝑛 (1≤𝑏𝑖≤109) on a separate line. It can be shown that at least one beautiful array exists under these circumstances. If there are multiple answers, print any of them.

Example
inputCopy
4
5
1 2 3 4 5
2
4 6
2
1 1000000000
6
3 4 8 1 2 3
outputCopy
3 3 3 3 3
3 6
1 1000000000
4 4 8 1 3 3

题意：
给你$a$数组，要求你构造$b$数组满足这三个条件

思路：
构造题，关键就在于1，相邻两个数之间填1是满足题意的，
因为两个数组对应数的差值绝对值是要小于两倍$a$数组和的，
所以又两种策略：

1. $b$数组奇数位置和$a$数组一样，偶数位置填1
2. $b$数组偶数位置和$a$数组一样，奇数位置填1

因为$a$数组奇数位置和与偶数位置和一定有一个大于等于数组一半，所以两种策略中一定有一个满足条件。

#include <algorithm>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>using namespace std;
typedef long long ll;
const int maxn = 1e3 + 7;
int a[55];
int main() {int T;scanf("%d",&T);while(T--) {int n;scanf("%d",&n);ll sum1 = 0,sum2 = 0;for(int i = 1;i <= n;i++) {scanf("%d",&a[i]);if(i & 1) sum1 += a[i];else sum2 += a[i];}if(sum1 >= sum2) {for(int i = 1;i <= n;i++) {if(i & 1) printf("%d ",a[i]);else printf("1 ");}} else {for(int i = 1;i <= n;i++) {if(!(i & 1)) printf("%d ",a[i]);else printf("1 ");}}printf("\n");}return 0;
}

这篇关于Codeforces 1463 B. Find The Array的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---