1899: 985的最大和难题

1899: 985的最大和难题

Time Limit: 1 Sec   Memory Limit: 128 MB Submit: 325   Solved: 39 Submit Status Web Board

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

221 1 12-10 20 -10

Sample Output

340

HINT

Source

hpu

如果n为奇数，则所有的负数都可以变为正数，否则，如果负数的个数为偶数则可以全部变为正数，为奇数的话最后会有一个负数剩余

#include<stdio.h> int main() { int sum,min,ans,t,n,i; int a[2010]; scanf("%d",&t); while(t--) { scanf("%d",&n); min=2000; sum=0; ans=0; for(i=1;i<2*n;i++) { scanf("%d",&a[i]); if(a[i]<0) { ans++; a[i]=-a[i]; } sum+=a[i]; if(a[i]<min) min=a[i]; } if(n%2) printf("%d\n",sum); else { if(ans%2==0) printf("%d\n",sum); else printf("%d\n",sum-2*min); } } return 0; }