个人任务13.K 次取反后最大化的数组和

た入场券 2023-09-28 13:33 63阅读 0赞

作者: Turbo 时间限制: 1S 章节: 课程设计

> **问题描述 :**  
> 给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：  
> 选择某个下标 i 并将 nums\[i\] 替换为 -nums\[i\] 。  
> 重复这个过程恰好 k 次。可以多次选择同一个下标 i 。  
> 以这种方式修改数组后，返回数组 可能的最大和 。  
> 示例 1：  
> 输入：  
> 3  
> 4 2 3  
> 1  
> 输出：5  
> 解释：选择下标 1 ，nums 变为 \[4,-2,3\] 。  
> 示例 2：  
> 输入：  
> 4  
> 3 -1 0 2  
> 3  
> 输出：6  
> 解释：选择下标 (1, 2, 2) ，nums 变为 \[3,1,0,2\] 。  
> 示例 3：  
> 输入：  
> 5  
> 2 -3 -1 5 -4  
> 2  
> 输出：13  
> 解释：选择下标 (1, 4) ，nums 变为 \[2,3,-1,5,4\] 。

> **输入说明 :**  
> 输入三行：  
> 第一行输入一个整数n表示数组nums的长度。  
> 第二行输入n个整数表示数组的元素。  
> 第三行输入一个整数表示k.  
> 提示：  
> 1 <= n <= 10^4  
> \-100 <= nums\[i\] <= 100  
> 1 <= k <= 10^4

> **输出说明 :**  
> 输出一个整数表示结果。

> **输入范例 :**  
> 4  
> 1 2 3 4  
> 3

> **输出范例 :**  
> 8

#include<iostream>
    #include<vector>
    #include<string>
    #include<sstream>
    #include<queue>
    #include<stack>
    #include<cmath>
    #include<algorithm>
    #include<cstring>
    #include<stdlib.h>
    #include<stdio.h>
    #include<fstream>
    #include<iomanip>
    #include<utility>
    using namespace std;
    int a[10001]={
        0},b[10001]={
        0};
    
    int Fanzhuan(int a[],int n,int m){
        
        int he=0;
        stable_sort(a,a+n);//先排好序，从小到大的顺序
        for(int i=0;i<n;++i){
        
            if(a[i]<0&&m>0){
        //如果有负数先把负数都变为正数
                a[i]=(-1*a[i]);
                --m;
            }
            he+=a[i];
        }
        stable_sort(a,a+n);//再对负数改正之后的数组排序
        return he-(m%2==0 ? 0 : 2*a[0]);//如果改变符号的次数是偶数个，最后和原数是一样的
    }                                   //如果是奇数个，就是差最小的数的2倍，所以要减去最小的数的2倍
    
    int main(){
        
        int n,m;
        cin>>n;
        for(int i=0;i<n;++i)
            cin>>a[i];
        cin>>m;
        cout<<Fanzhuan(a,n,m);
        return 0;
    }