問題
https://codeforces.com/contest/1546/problem/A (新しいタブで開く)
問題文
数列 が与えられる。以下の操作を何回か行うことで、 とできるか?
できる場合は、その方法を示す。複数あるならどれでもよい。
ただし、操作回数を最小化しなくてもよい。
となる を選ぶ。 ( でもよい)
を 1 減らし、 を 1 増やす。
ただし、 の各要素は 以上でなければならない。
制約
- の総和は 100 を超えない
サンプル
4 4 1 2 3 4 3 1 2 4 2 1 3 2 1 1 0 0 5 4 3 2 1 0 0 1 2 3 4
2 2 1 3 1 -1 0 6 1 4 1 4 1 5 1 5 2 5 2 5
考察
もし なら、不可能。
そうではない場合、前から順番に を に合わせて行く。
総和が等しいので、増やす回数/減らす回数は同じ個数になるはず。
コード
https://codeforces.com/contest/1546/submission/122079157 (新しいタブで開く)
void solve() { int n; cin >> n; vector<int> a(n), b(n); int sum = 0; rep(i, n) { cin >> a[i]; sum += a[i]; } rep(i, n) { cin >> b[i]; sum -= b[i]; } if (sum != 0) { cout << -1 << endl; return; } vector<int> plus, minus; rep(i, n) { if (a[i] - b[i] > 0) { rep(__, a[i] - b[i]) { minus.push_back(i + 1); } } else if (a[i] - b[i] < 0) { rep(__, b[i] - a[i]) { plus.push_back(i + 1); } } } cout << minus.size() << endl; rep(i, minus.size()) { cout << minus[i] << " " << plus[i] << endl; } return; }