【郑轻】[1899]985的最大和难题

问题描述

985的最大和难题

时间限制：1 Sec内存限制：128 MB

Description

985有2 * n - 1个整数，他每次可以将其中n个数变号，操作次数不限，问他可以得到的最大和。

Input

第一行输入一个整数t，代表有t组测试数据。
每组数据占两行，第一行输入一个整数n，下面一行输入2*n-1个整数a[]。
注：1 <= t <= 32，1 <= n <= 1e3，-1e3 <= a[] <= 1e3。

Output

输出一个整数代表可以得到的最大和。

Sample Input

Sample Output

  3
40

问题分析

n=3时的负数变化
(0为负数1为正数)
有一个：

有两个：

有三个：

  0 0 0 1 1

1 1 1 1 1

总结规律：

负数	正数
0	2n-1
n	n-1
1	2n-2
n-1	n
3	2n-4
n-3	n+2
……	……

可发现若n为奇数时
总可以把负数全部变为正数
当n为偶数时
每次能改变偶数个负数
所以若负数的个数为偶数个
也能全部变为正数
当负数的个数为奇数个总会留下一个数为负数
(但不一定是原来就有的负数)
为了让总和最大
可以使绝对值最小的数为负数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<stdio.h> 
int main() { 
    int T; 
    scanf("%d",&T); 
    while(T--) { 
        int n; 
        scanf("%d",&n); 
        int l=2*n-1; 
        int sum=0,cnt=0,res=99999999; 
        for(int i=0; i<l; i++) { 
            int t; 
            scanf("%d",&t); 
            if(t<0) { 
                cnt++; 
                t=-t; 
            } 
            if(res>t) 
                res=t; 
            sum+=t; 
        } 
        if(n&1||cnt%2==0) 
            printf("%d\n",sum); 
        else
            printf("%d\n",sum-2*res); 
    } 
    return 0; 
}

题目地址:【郑轻】[1899]985的最大和难题