結果
問題 | No.198 キャンディー・ボックス2 |
ユーザー |
![]() |
提出日時 | 2016-03-27 01:56:50 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 1,000 ms |
コード長 | 1,301 bytes |
コンパイル時間 | 798 ms |
コンパイル使用メモリ | 84,580 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-16 09:55:27 |
合計ジャッジ時間 | 1,505 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 26 |
ソースコード
/* -*- coding: utf-8 -*- * * 198.cc: No.198 キャンディー・ボックス2 - yukicoder */ #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<string> #include<vector> #include<map> #include<set> #include<stack> #include<list> #include<queue> #include<deque> #include<algorithm> #include<numeric> #include<utility> #include<complex> #include<functional> using namespace std; /* constant */ const int MAX_N = 10; /* typedef */ typedef long long ll; /* global variables */ ll cs[MAX_N]; /* subroutines */ ll steps(int n, ll a) { ll d = 0; for (int i = 0; i < n; i++) d += (cs[i] > a) ? cs[i] - a : a - cs[i]; return d; } /* main */ int main() { ll b; int n; cin >> b >> n; ll sum = 0; for (int i = 0; i < n; i++) { cin >> cs[i]; sum += cs[i]; } ll c0 = -1, c1 = (sum + b) / n; while (c0 + 2 < c1) { ll a0 = (c0 * 2 + c1) / 3; ll a1 = (c0 + c1 * 2) / 3; if (steps(n, a0) <= steps(n, a1)) c1 = a1; else c0 = a0; } //printf("steps(%lld)=%lld, steps(%lld)=%lld\n", //c0, steps(n, c0), c1, steps(n, c1)); ll mins = steps(n, c0); ll s1 = steps(n, c0 + 1); ll s2 = steps(n, c0 + 2); if (mins > s1) mins = s1; if (mins > s2) mins = s2; printf("%lld\n", mins); return 0; }