CODEFORCES #182 Div2 C. Yaroslav and Sequence
(1)nが奇数の時
例1. n = 3の時、符号だけに着目すると
[1] +++++
[2] ++++-
[3] +++--
[4] ++---
[5] +----
[6] -----
操作で
(6)→(3)→(4)→(1)
(5)→(2)→(3)
と何回かの操作ですべての場合に対して符号を正にできる。
(2)nが偶数の時
(2-1)入力列の正の符号が奇数個の場合は(1)の時と同様に、何回かの操作ですべて場合に対して符号を正にできる。
(2-2)入力列の正の符号が偶数個の場合は、1つの符号が負で、残りの符号を正の列に変換できる。
#include <iostream> #include <algorithm> using namespace std; int main() { int n, sum, p, tmp, min_all; sum = p = 0; min_all = 10000; cin >> n; for (int i = 0; i < 2 * n - 1; i++) { cin >> tmp; if (tmp >= 0) p++; else tmp *= -1; sum += tmp; min_all = min(min_all, tmp); } if (n % 2 == 1 || (n % 2 == 0 && p % 2 == 1)) cout << sum << endl; else cout << sum - 2 * min_all << endl; return 0; }