1899: 985的最大和难题

Time Limit: 1 Sec  Memory Limit: 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。

</div>

Output

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

Sample Input

2
2
1 1 1
2
-10 20 -10

Sample Output

3
40


n=3时的负数变化

(0为负数1为正数)
有一个:
0 1 1 1 1
1 0 0 1 1
1 0 1 0 0
1 1 1 1 1
有两个:
0 0 1 1 1
0 1 0 0 1

1 1 1 1 1
有三个:
0 0 0 1 1

1 1 1 1 1

总结规律:


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

可发现若n为奇数时

总可以把负数全部变为正数

当n为偶数时

每次能改变偶数个负数

所以若负数的个数为偶数个

也能全部变为正数

当负数的个数为奇数个

总会留下一个数为负数

(但不一定是原来就有的负数)

为了让总和最大

可以使绝对值最小的数为负数


#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的最大和难题

© DiDaPiPa all right reserved,powered by GitbookRevision Time: 2020-03-12 21:32:06

results matching ""

    No results matching ""