A - AquaMoon and Two Arrays

cpcodeforcesdiv2greedy

最終更新日

問題

https://codeforces.com/contest/1546/problem/A (新しいタブで開く)

問題文

数列 a,ba, b が与えられる。以下の操作を何回か行うことで、 a=ba = b とできるか?
できる場合は、その方法を示す。複数あるならどれでもよい。
ただし、操作回数を最小化しなくてもよい。

1i,jn1 \le i, j \le n となる i,ji, j を選ぶ。 (i=ji = j でもよい)
aia_i を 1 減らし、 aja_j を 1 増やす。
ただし、 aa の各要素は 00 以上でなければならない。

制約

サンプル

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

考察

もし aibi\sum a_i \ne \sum b_i なら、不可能。
そうではない場合、前から順番に aia_ibib_i に合わせて行く。
総和が等しいので、増やす回数/減らす回数は同じ個数になるはず。

コード

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