結果

問題 No.198 キャンディー・ボックス２
コンテスト
ユーザー Toshokahn
提出日時 2019-11-06 15:52:32
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 2 ms / 1,000 ms
コード長 1,575 bytes
コンパイル時間 1,287 ms
コンパイル使用メモリ 160,624 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-15 00:20:18
合計ジャッジ時間 2,428 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 26
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:100:14: warning: ‘ans’ may be used uninitialized in this function [-Wmaybe-uninitialized]
  100 |   cout << f(x) << endl;
      |              ^

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repp(i, a, b) for (int i = a; i <= (b); ++i)
const int INF = 1001001001;
const ll LINF = 1001001001001001001ll;

template <class T>
inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}

template <class T>
inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
/*
  凸関数fに対し
  argmax/min f
  を返す。

  ※凸関数でないとダメ
 */

template <class T>
T find_max(T l, T r, T f(T)) {
  T cl, cr;
  while (r - l > 3) {
    cl = (l * 2 + r) / 3, cr = (l + r * 2) / 3;
    if (f(cl) < f(cr))
      l = cl;
    else
      r = cr;
  }

  T ans;
  T fmax = numeric_limits<T>::min();
  repp(i, l, r) {
    if (chmax(fmax, f(i)))
      ans = i;
  }
  return ans;
}

template <class T>
T find_min(T l, T r, T f(T)) {
  T cl, cr;
  while (r - l > 3) {
    cl = (l * 2 + r) / 3, cr = (l + r * 2) / 3;
    if (f(cl) > f(cr))
      l = cl;
    else
      r = cr;
  }

  T ans;
  T fmin = numeric_limits<T>::max();
  repp(i, l, r) {
    if (chmin(fmin, f(i)))
      ans = i;
  }
  return ans;
}

/*
https://yukicoder.me/problems/no/198
*/

vector<ll> C;
ll B, N;

ll f(ll x) {
  ll cnt = 0;
  ll num = 0;
  rep(i, N) {
    cnt += abs(C[i] - x);
    num += C[i];
  }

  if (num + B < x * N)
    cnt = LINF;
  return cnt;
}

int main() {
  cin >> B >> N;
  C = vector<ll>(N);
  rep(i, N) cin >> C[i];

  ll x = find_min(0LL, (ll)INF, f);
  cout << f(x) << endl;
}
0