結果
問題 | No.198 キャンディー・ボックス2 |
ユーザー |
![]() |
提出日時 | 2015-04-29 00:03:19 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 1,000 ms |
コード長 | 1,003 bytes |
コンパイル時間 | 1,677 ms |
コンパイル使用メモリ | 162,720 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-16 08:57:40 |
合計ジャッジ時間 | 2,668 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 26 |
ソースコード
#include <bits/stdc++.h> using namespace std; vector<long long> A; double f(double x){ double cnt = 0; for(int i = 0 ; i < A.size() ; i++) cnt += fabs(A[i]-x); return -cnt; } long long g(long long x){ long long cnt = 0; for(int i = 0 ; i < A.size() ; i++) cnt += abs(A[i]-x); return cnt; } double search(double left, double right) { for (int loop = 0; loop < 1919; ++loop){ if (f((left * 2 + right) / 3) > f((left + right * 2) / 3)){ right = (left + right * 2) / 3; } else { left = (left * 2 + right) / 3; } } return (right + left) * 0.5; } int main(){ long long B,N; cin >> B >> N; vector<long long> C(N); long long sum = B; for(int i = 0 ; i < N ; i++){ cin >> C[i]; sum += C[i]; } ::A = C; sum /= N; //cout << search(0,sum) << endl; //cout << f(720) << "<" << endl; long long ans = 1e15; long long X = search(0,sum); //cout << X << endl; for(int i = -1145 ; i <= 1419 ; i++){ if( X+i <= sum ) ans = min(g(X + i),ans); } cout << ans << endl; }