A. Sign Flipping (Codeforces Global Round 9)

こういう問題、苦手です・・・。

問題

https://codeforces.com/contest/1375/problem/A

問題概要

長さnの数列が与えられる。あなたは各項の符号を自由に変えることができる。

符号を変えることで、与えられた数列を以下の条件を満たす数列に変形せよ。

• となるようなiを少なくとも個にする
• となるようなiを少なくとも個にする

考察

正数から負数を引くと正数となります。また、負数から正数を引くと負数になります。

よって、数列の各項を「正数、負数、正数、負数、正数、・・・」と並べていくと、i=1について正数、i=2について負数・・・、と正数と負数が交互に現れるため半数が正数、もう半数が負数となり条件をちょうど満たすことができます。

なお、0が一つ含まれている分には結果に影響を与えませんし、0が並んでいる場合は、差が0になり両方の条件を満たせるのでこれも問題ありません。

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        int a;
        for (int i = 0; i < n; i++) {
            cin >> a;
            if (i % 2 == 0) cout << abs(a) << (i == n - 1 ? '\n' : ' ');
            else cout << -abs(a) << ' ';
        }
    }
}