CFR 301 A. Yaroslav and Sequence ( Greedy )

題意：
給一個長度為 2 * N - 1 的數列 A。你可以進行任意次以下的操作：
選擇任意 N 個相異的元素，讓他們的符號反轉 ( 乘上 -1 )。
問操作後，可以得到的最大數列和為何。

資料規模：
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.

解法：
考慮不變量。首先注意到做一次操作後，只要再做一次操作，將其中一個進行過操作的 i 改成一個未進行操作的 j。這麼一來，很顯然我們可以只改 i 和 j 的符號。可以發現，如果 N 是偶數，那麼無論怎麼進行操作，負號的數量的奇偶性不會改變，並且在此前提下，這個數量可以是任意的，套用的對象也可以是任意的。至於 N 是奇數的情況，這個奇偶性是可以改變的，因此可以將所有元素變正。注意如果 A 中有 0，那麼顯然也是可以讓所有元素變正。

時間 / 空間複雜度：
O( N )

N = int( input() )
A = list( map( int, input().split() ) )

neg = sum( A[ i ] < 0 for i in range( len( A ) ) )
if 0 in A or N % 2 == 0:
  neg = 0

B = sorted( [ abs( A[ i ] ) for i in range( len( A ) ) ] )
if neg & 1:
  print( - abs( B[ 0 ] ) + sum( B[ i ] for i in range( 1, len( B ), 1 ) ) )
else:
  print( sum( B[ i ] for i in range( len( B ) ) ) )