AtCoder Regular Contest 059 C - いっしょ

問題

問題文へ

与えられたN個の整数を、書き換えてすべて同じ整数にします。1つの整数に対して、次の操作を一度だけ行えます。

整数をxを整数yに書き換える時、のコストがかかります。

すべて同じ整数にするための必要な最小のコストを求めます。

制約

• 
• 

考えたこと

与えられる整数は最大100個です。書き換える整数は、a_iの取り得る範囲内に収まると思います。

100を200にする必要はなく、与えられた数列の中心へ向かうと考えました。

与えられる整数の個数と試す範囲も狭いため、すべてを試しました。

コード

#define _GIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;


int main(void) {
  int N;
  cin >> N;
  vector<ll> a(N);
  rep(i, N) cin >> a[i];

  ll ans = 10000000000;
  for (ll c = -100; c <= 100; ++c) {
    ll cost = 0;
    rep(i, N) {
      cost += (a[i] - c) * (a[i] - c);
    }

    ans = min(ans, cost);
  }

  cout << ans << endl;
  
  return 0;
}

解説を読んで

とくにありません。