結果
問題 | No.198 キャンディー・ボックス2 |
ユーザー |
![]() |
提出日時 | 2023-11-06 00:12:25 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 1,000 ms |
コード長 | 1,481 bytes |
コンパイル時間 | 2,201 ms |
コンパイル使用メモリ | 198,484 KB |
最終ジャッジ日時 | 2025-02-17 19:42:59 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 26 |
ソースコード
#include <bits/stdc++.h> #include<iostream> #include<iomanip> #include<string> #include<algorithm> #include<vector> #include<set> #include<list> #include<queue> #include<math.h> #include<bitset> using ll = long long; using namespace std; ll solve(vector<int> &v, ll bt, ll t1, ll t2 = -1){ ll ret = 1e10; if (t2 == -1) t2 = t1; if (t1 > t2) swap(t1, t2); for (ll i = 0; i < 2; i++){ if (i == 1) t1 = t2; ll ans = 0, b = bt; for (int j = 0; j < v.size(); j++){ if (v[j] > t1) { b += (v[j] - t1); ans += (v[j] - t1); } } for (int j = 0; j < v.size(); j++){ if (v[j] < t1) { if (b >= (t1 - v[j])) { b -= (t1 - v[j]); ans += (t1 - v[j]); } } } ret = min(ret, ans); } return ret; } int main(){ ll b, n, t1, t2, ave = 0, ans = 0; cin >> b >> n; vector<int> v(n); for (int i = 0; i < n; i++) { cin >> v[i]; ave += v[i]; } ave += b; ave /= n; sort(v.begin(), v.end()); if (n%2) { t1 = v[n/2]; if (ave < t1) t1 = ave; ans = solve(v, b, t1); } else { t2 = v[n/2]; t1 = v[n/2 - 1]; if (ave < t1) { t1 = ave; t2 = ave; } if (ave < t2) t2 = ave; ans = solve(v, b, t1, t2); } cout << ans << endl; }