题意翻译

你有一个长度为$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

0

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;
}

THE END