题意翻译

你有一个长度为$n$的数组$a$。

你可以进行任意次操作，每一次可以选择一个数$a_i$，并让$a_i$变成$-a_i-1$。

你的目标是使得这个数组每一个元素的乘积最大，请求出这个最大的价值，并输出这个最大价值的序列。

输入格式

第一行包含一个整数$n$，表示数组的长度。

第二行包含$n$个整数，分别为$a_1…… a_n$，表示数组中的元素。

输出格式

输出仅有一行，包含$n$个整数，表示这个最大的价值序列。

Input & Output ‘s examples

Input ‘s eg 1

4
2 2 2 2

Output ‘s eg 1

-3 -3 -3 -3

Input ‘s eg 2

1
0

Output ‘s eg 2

Input ‘s eg 3

3
-3 -3 2

Output ‘s eg 3

-3 -3 2

数据范围和约定

对于$100\%$的数据，保证$1 < n < 10^5$，$-10^6 < a_i < 10^6$

分析

一道简单贪心题。

手推几组样例后不难看出，一个数如果操作两次之后等于没操作。则题目就变成了对于每一个$a_i$，让你选择是否进行操作，使得乘积最大。

可以注意到，若$a_i$是一个正数，则$|- a_i - 1|$一定大于$n$。

又根据初中数学可得，偶数个负数的乘积一定是正数。

因此，对于$n$是偶数的情况我们直接全部变成负数即可。

而对于$n$为奇数的情况，不难看出，奇数减$1$一定是偶数。因此，我们只需要选择一个数不进行操作即可。

显然，我们要选择的是绝对值最大的数。

时间复杂度为$O(n)$，跑过$10^5$的数据绰绰有余。

剩下的见代码注释。

Code[Accepted]

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<deque>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<cstdlib>
#include<cctype>
#include<cmath>

#define ll long long
#define I inline
#define N 100001

using namespace std;

ll n , a[N];
ll maxn = 0;
ll p = 0x3f3f3f3f;

int main(){
    cin >> n;
    for(int i = 1; i <= n; i ++){
        cin >> a[i];
        if(a[i] >= 0){          //输入时将所有的数都变成负数
            a[i] = -a[i] - 1;
        }
        maxn = min(maxn , a[i]);
        if(maxn == a[i]){       //记录绝对值最大的数的位置
            p = i;
        }
    }
    if(n % 2 == 0){     //如果n为偶数，直接输出序列即可。
        for(int i = 1; i <= n; i ++){
            cout << a[i] << " ";
        }
        return 0;
    }
    else{
        for(int i = 1; i <= n; i ++){   //否则的话，修改绝对值最大的数。
            if(p == i){
                cout << -a[i] - 1 << " ";
            }
            else{
                cout << a[i] << " ";
            }
        }
    }
    return 0;
}