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