CF1180B题解

skyskyCCC · 2022-04-25 13:43:58 · 题解

前言。

数学题与贪心的结合。

分析。

题意传送门。

这个题要用到绝对值。绝对值的基本情况：

• 绝对值的定义：一个实数在数轴上离原点的距离
• 绝对值的规律：当该数是正数时，绝对值等于该数，是负数时，是其相反数。

详情请看这里。

如果一个数操作两次，那么仍是原数。

就是说每次选择每一个数是 a_i 还是 -a_i-1 的操作，使得总乘积最大。

证明过程：

已知正数 a_i 的绝对值为 |a_i|=a_i，负数 a_i 的绝对值为 |a_i|=-a_i。

那么，对于正数来说的 |-a_i-1| 一定大于 |a_i|=a_i。

反之，对于负数来说的 |-a_i-1| 一定小于 |a_i|=-a_i。

又因偶数个负数之积为正数，所以我们将偶数个负数相乘会使总价值最大。

很显然，我们将正数转换为负数，总价值最大。

当 n 为偶数个时，只要将正数化为负数，将负数一一相乘就行了。但是，当 n 为奇数个时，要使总价值最大，只能将其中绝对值最大的数不变，使其它的数与其相乘最大。

证毕。

详细过程请见代码。

代码如下，仅供参考：

#include<iostream>
#include<cmath>//min函数在里面。
using namespace std;
int n,a[100005],minn=0;
int ans=0x3f3f3f3f;//要设的尽可能大。
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(a[i]>=0) a[i]=-a[i]-1;//如果是正数，就将其转换成负数，使数组中都是负数。
        minn=min(minn,a[i]);//找最大值。
        if(minn==a[i]) ans=i;//找到绝对值最大的数的下标。
    }
    if(n%2==1){//当n为奇数的情况。
        for(int i=1;i<=n;i++){
            if(ans==i) cout<<-a[i]-1<<" ";
            //找到绝对值最大的数，将其再转化成正数。
            else cout<<a[i]<<" ";//其它负数直接输出。
        }
        return 0;//阶段性结束。
    }
    if(n%2==0){//当n为偶数的情况。
        for(int i=1;i<=n;i++){
            cout<<a[i]<<" "；//输出数组即可。
        }
    }
    return 0;//真正的终结。
}//by zzy

后记。

无。