問題
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;
}