Codeforces #182 Div2 C "Yaroslav and Sequence"
問題
http://codeforces.com/contest/302/problem/C
訳
ヤロスラフは2 * n - 1個の整数からなる配列を持っている。
1回の操作で、ヤロスラフは配列のちょうどn個の要素の符号を変える事ができる。
言い換えると、1回の操作で、ヤロスラフはちょうどn個の要素を選び、
そして各要素に -1 を掛けることが出来る。
ヤロスラフは今、上記の操作を好きなだけ行ったとき、配
列の要素の総和の最大値はどのくらいだろうか?と考えている。
ヤロスラフを助けて!
制約
2 <= n <= 100
-1000 <= 配列の要素の値 <= 1000
解法
紙に書き出してみると分かるが、
nが奇数のとき、
上手く要素を選び出せば要素の符号を好きなように変えることができる。
よって、0未満の要素があれば、符号をプラスにすればよい。
nが偶数のとき、
偶数個の要素の符号を、好きなように変えることが出来る。
(0個, 2個, 4個, ... , (n-1) * 2個 )
よって、配列をソートして、一番小さい要素から2つずつ符号を逆転していって、
合計の最大値をとっていけばよい。
ソースコード
int a[210]; int main() { int N; cin >> N; int n = N * 2 - 1; int res = 0; for( int i = 0; i < n; i++ ){ cin >> a[i]; res += a[i]; } sort( a, a + n ); // 奇数 if( N % 2 ){ for( int i = 0; i < n; i++ ){ if( a[i] < 0 ){ res += -a[i] * 2; } } }else{ // 偶数 for( int i = 0; i + 1 < n - 1; i += 2 ){ int add = 0; if( a[i] < 0 ){ add += -a[i] * 2; }else{ add -= a[i] * 2; } if( a[i+1] < 0 ){ add += -a[i+1] * 2; }else{ add -= a[i+1] * 2; } if( add > 0 ){ res += add; } } } cout << res << endl; }