题目描述

难度分:$1500$

输入$n(1 \leq n \leq 10^5)$和长为$n$的数组$a(-10^6 \leq a[i] \leq 10^6)$。

你可以执行如下操作任意次：

• 选择一个$a[i]$，把它替换为$-a[i]-1$。

你需要让所有数的乘积最大。
输出修改后的数组。

输入样例$1$

4
2 2 2 2

输出样例$1$

-3 -3 -3 -3 

输入样例$2$

1
0

输出样例$2$

0

输入样例$3$

3
-3 -3 2

输出样例$3$

-3 -3 2

算法

贪心

可以比较容易发现，对一个非负数操作可以获得更大的绝对值。

1. 如果数组长度$n$为偶数，那直接把所有非负数操作成负数就可以了，反正$n$为偶数，负负得正可以得到最大的乘积。
2. 否则，假设$a$中所有非负数都已经做过操作，此时会多余一个负数（其他偶数个负数能够乘出一个正的乘积），把绝对值最大的那个负数再变成非负数就行，其他负数相乘得到的结果是正数，再和这个非负数相乘仍然是非负数。

复杂度分析

时间复杂度

整个算法就只是对$a$进行了一次遍历，然后通过数组长度$n$来分情况输出修改过后的数组，因此时间复杂度为$O(n)$。

空间复杂度

除了输入的数组$a$，只使用了有限几个变量，因此额外空间复杂度为$O(1)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 100010;
int a[N];

int main() {
    int n;
    scanf("%d", &n);
    int t = 1;
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        if(a[i] >= 0) {
            a[i] = -a[i] - 1;
        }
        if(a[i] < a[t]) {
            t = i;
        }
    }
    if(n&1) {
        a[t] = -a[t] - 1;
    }
    for(int i = 1; i <= n; i++) {
        printf("%d ", a[i]);
    }
    return 0;
}