// competitive-verifier: PROBLEM https://yukicoder.me/problems/no/198
#include "Other/fibonacci_search.hpp"
#include <bits/stdc++.h>
using namespace std;
int main()
{
long long B, N;
cin >> B >> N;
vector<long long> C(N);
for (int i = 0; i < N; i++)
{
cin >> C[i];
B += C[i];
}
auto f = [&](long long x) -> long long
{
long long sum = 0;
for (int i = 0; i < N; i++)
{
sum += abs(C[i] - x);
}
return sum;
};
auto [x, fx] = fibonacci_search<true, long long>(0, B / N, f);
cout << fx << endl;
return 0;
};
#line 1 "test/Other/fibonacci_search/yukicoder-198.cpp"
// competitive-verifier: PROBLEM https://yukicoder.me/problems/no/198
#line 1 "Other/fibonacci_search.hpp"
#include <bits/stdc++.h>
using namespace std;
// フィボナッチ数列による三分探索。「狭義」凸関数の極値を探索する。返り値は{x, f(x)}
template <bool Minimize, typename T>
pair<long long, T> fibonacci_search(long long x_low, long long x_high, function<T(long long)> f)
{
assert(x_low <= x_high);
long long offset = x_low;
T INF = Minimize ? numeric_limits<T>::max() : numeric_limits<T>::lowest();
auto comp = [](T a, T b) -> bool
{
return Minimize ? a <= b : a >= b;
};
vector<long long> fib = {1, 1};
while (fib.back() <= x_high - offset)
{
fib.push_back(fib[fib.size() - 1] + fib[fib.size() - 2]);
}
unordered_map<long long, T> fx_cache;
auto eval = [&](long long idx) -> T
{
long long x = idx + offset;
if (x_low <= x && x <= x_high)
{
if (!fx_cache.contains(x))
{
fx_cache[x] = f(x);
}
return fx_cache[x];
}
return INF;
};
long long l_idx = 0, r_idx = fib.back();
while (2 <= fib.size())
{
long long step_len = fib[fib.size() - 2];
long long mid_l_idx = r_idx - step_len, mid_r_idx = l_idx + step_len;
T fl = eval(mid_l_idx), fr = eval(mid_r_idx);
if (comp(fl, fr))
{
r_idx = mid_r_idx;
}
else
{
l_idx = mid_l_idx;
}
fib.pop_back();
}
if (comp(eval(l_idx), eval(r_idx)))
{
return {l_idx + offset, eval(l_idx)};
}
else
{
return {r_idx + offset, eval(r_idx)};
}
}
#line 5 "test/Other/fibonacci_search/yukicoder-198.cpp"
using namespace std;
int main()
{
long long B, N;
cin >> B >> N;
vector<long long> C(N);
for (int i = 0; i < N; i++)
{
cin >> C[i];
B += C[i];
}
auto f = [&](long long x) -> long long
{
long long sum = 0;
for (int i = 0; i < N; i++)
{
sum += abs(C[i] - x);
}
return sum;
};
auto [x, fx] = fibonacci_search<true, long long>(0, B / N, f);
cout << fx << endl;
return 0;
};
test/Other/fibonacci_search/yukicoder-198.cpp