1899: 985的最大和难题
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 329 Solved: 41
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
2 2 1 1 1 2 -10 20 -10
Sample Output
3 40
题目链接 http://acm.zzuli.edu.cn/zzuliacm/problem.php?id=1899
考思维啊自己做时是万万想不到啊，还是做题少。。。智商也跟不上。。
#include<cstdio>
#include<algorithm> using namespace std; int main() { int t; scanf("%d",&t); while(t--) { int n,a; int zheng=0,fu=0; scanf("%d",&n); int m=2*n-1; int minm=1e5+10; int sum=0; for(int i=1;i<=m;i++) { scanf("%d",&a); if(a<0) a=-a,fu++; elsezheng++; sum+=a; minm=min(minm,a); } if(n%2!=0)//n为奇数 printf("%d\n",sum);//n为奇数时，每次变换n个可以增加或减少一个负数， //因为次数不限，可以全部转化为正数 else//n为偶数时 ，每次改变n1个可以增加或减少2个负数 { if(fu%2!=0)//负数个数为奇数个，不能全部转化为正数 把最小的转化为负数 printf("%d\n",sum-2*minm); elseprintf("%d\n",sum); } } return 0; } /************************************************************** Problem: 1899 User: wry Language: C++ Result: Accepted Time:1 ms Memory:872 kb ****************************************************************/
