問題
https://codeforces.com/contest/1399/problem/B (新しいタブで開く)
問題文
個のギフトがあって、全部同じ数にしたい。
そのために、以下の操作を何回か行う。
1 つのギフトを選ぶ。
そして、 か 、もしくはその両方を 減らす。
任意の について、 かつ としたい。( でなくてもいい)
最小で何回操作が必要?
制約
サンプル
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
考察
と の最小値以下にそれぞれを減らす必要はない。
また、 と の両方を減らしたいときは、2 つ同時に減らして、余ったほうを減らすのが最適。このときの操作回数は になる。
よって、答えは
コード
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; }