1899: 985的最大和难题
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 319 Solved: 37
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
2*n-1个数，它是一个奇数，如果n时奇数，有a个负数，b个整数，(a+b)==n;所以可以把又有的负数
变成正数，举例 n=7;n=3+4;每次换都可以减少一个负数，增加一个偶数
n为偶数时那就有2种情况 1、负数的个数是 y，y如果是偶数就可以把所有的负数转化为正数
2、 y为奇数，那肯定会剩下一个负数 (完@_@)
#include<cstdio>
#include<algorithm>
using namespace std;
int num[1000000+11];int main()
{int t;scanf("%d",&t);while(t--){int n,i;scanf("%d",&n);int sum=0,y=0;for(i=0;i<2*n-1;++i){scanf("%d",&num[i]);if(num[i]<0){num[i]=-num[i];++y;}sum+=num[i];}if(n&1)printf("%d\n",sum);else{if(y&1){sort(num,num+2*n-1);sum-=2*num[0];//一定要*2倍，因为刚开始已经加过了 printf("%d\n",sum);}elseprintf("%d\n",sum);}}return 0;
}
