本当にただ全探索するだけ!!!
でも意外とこういうのが思いつかれにくいかもしれない。
問題概要 (意訳)
長さ の整数列 が与えられる。今、整数 を 1 つ選ぶ。そして整数列をすべて に書き換える。それに要するコストは
で与えられる。適切に を選んだときの、コストの最小値を求めよ。
制約
考えたこと
の最小値を 、最大値を としたとき、
- より小さい は試す必要がない
- より大きい は試す必要がない
ということがいえる。よってこの時点で、 の候補は 以上 以下の整数値のみに限られた。これらをすべて調べて、その最小値を求めれば OK。計算量は となる。
#include <bits/stdc++.h> using namespace std; int main() { int N; cin >> N; vector<long long> a(N); for (int i = 0; i < N; ++i) cin >> a[i]; long long res = 1LL<<60; for (int x = -100; x <= 100; ++x) { long long tmp = 0; for (int i = 0; i < N; ++i) tmp += (x - a[i]) * (x - a[i]); res = min(res, tmp); } cout << res << endl; }