AtCoder Regular Contest 122B

ARC122B

\(x \in \mathbb{R}\) であるから，範囲を狭くしたい． min を外すため，大小で場合分けする． 場合分けの境目の値が候補になりそうで， 実際にそうなる． これで候補が \(N\) 個に絞れたので全探索できる．
実装
\(a\) の中に同じ値が複数ある場合に注意． \(for \ i \in N\) を動かしながら，

• 今までの \(a_{i}\) の個数
• 今までの \(a_{i}\) の和

を保持する．

使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"

int main() {

  ll n;

  cin >> n;

  vll a(n); rep(i,n) { cin >> a[i]; }

  ll tot = 0;

  set<ll> st;

  map<ll,ll> mp; // count

  rep(i,n){

    st.insert(a[i]);

    mp[a[i]]++;

    tot += a[i];

  }

  ll cnt = 0;

  ll sum = 0;

  double ans = 1e18;

  for(auto y:st){

    double x = (double)y / 2;

    double now = ( 2*cnt - n ) * x + double(tot - sum);

    chmin(ans, now);

    sum += mp[y]*y;

    cnt += mp[y];

  }

  printf("%.10lf", ans / n);

  return 0;

}