B - Gifts Fixing

cpcodeforcesdiv3greedy

最終更新日

問題

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

問題文

nn 個のギフトがあって、全部同じ数にしたい。
そのために、以下の操作を何回か行う。

1 つのギフトを選ぶ。
そして、 aia_ibib_i 、もしくはその両方を 11 減らす。

任意の i,ji, j について、 ai=aja_i = a_j かつ bi=bjb_i = b_j としたい。(ai=bia_i = b_i でなくてもいい)
最小で何回操作が必要?

制約

サンプル

5
3
3 5 6
3 2 3
5
1 2 3 4 5
5 4 3 2 1
3
1 1 1
2 2 2
6
1 1000000000 1000000000 1000000000 1000000000 1000000000
1 1 1 1 1 1
3
10 12 8
7 5 4
6
16
0
4999999995
7

考察

aia_ibib_i の最小値以下にそれぞれを減らす必要はない。
また、 aia_ibib_i の両方を減らしたいときは、2 つ同時に減らして、余ったほうを減らすのが最適。このときの操作回数は max(aimina,biminb)\max(a_i - \min a, b_i - \min b) になる。

よって、答えは (max(aimina,biminb))\sum (\max(a_i - \min a, b_i - \min b))

コード

https://codeforces.com/contest/1399/submission/126143962 (新しいタブで開く)

void solve() {
  int n;
  cin >> n;
  vector<ll> a(n), b(n);
  ll mina = 1e9, minb = 1e9;
  rep(i, n) {
    cin >> a[i];
    mina = min(mina, a[i]);
  }
  rep(i, n) {
    cin >> b[i];
    minb = min(minb, b[i]);
  }
  ll ans = 0;
  rep(i, n) {
    ll ca = a[i] - mina;
    ll cb = b[i] - minb;
    ans += max(ca, cb);
  }
  cout << ans << endl;
}