2 seconds
256 megabytes
standard input
standard output
Yaroslav has an array, consisting of (2·n - 1) integers. In a single operation Yaroslav can change the sign of exactly n elements
in the array. In other words, in one operation Yaroslav can select exactly n array elements, and multiply each of them by -1.
Yaroslav is now wondering: what maximum sum of array elements can be obtained if it is allowed to perform any number of described operations?
Help Yaroslav.
The first line contains an integer n (2 ≤ n ≤ 100).
The second line contains (2·n - 1) integers — the array elements. The array elements do not exceed 1000 in
their absolute value.
In a single line print the answer to the problem — the maximum sum that Yaroslav can get.
2 50 50 50
150
2 -1 -100 -1
100
In the first sample you do not need to change anything. The sum of elements equals 150.
In the second sample you need to change the sign of the first two elements. Then we get the sum of the elements equal to 100.
1 1 1 1,Yaroslav一次只能改变这数列其中3个元素的符号使其变成-1 -1 -1 1 1或者1 1 -1 -1 -1等等),现在问题是允许Yaroslav无数次重复这个操作(即一次改变n个元素的符号)怎样才能得到最大的数列和?下面就说这道题的思路:
const int MAX=10000;
int s[MAX];
using namespace std;
int main()
{
int n,i,j,fushu,sum,MIN;
cin>>n;
fushu=0;
sum=0;
MIN=MAX;
for(i=1;i<=2*n-1;i++)
{
cin>>s[i];
if(s[i]<0)
{
fushu+=1;
s[i]=-s[i];
}
if(s[i]<MIN)
MIN=s[i];
sum+=s[i];
}
if(n%2!=0)
{
cout<<sum<<endl;
}
else
{
if(fushu%2!=0)
cout<<sum-MIN*2<<endl;
else
cout<<sum<<endl;
}
return 0;
}//如果有问题,或有什么疑惑,可以在评论中提出,小子我看到一定尽力解答