Yukicoder021 平均の差

問題概要

$N$個の数字$n[i]$が与えられるので$K$個のグループに分ける。 それぞれのグループについて平均を求め、グループ間の平均値の最大-最小を最大化せよ。

$3\leqq N\leqq9$、$3\leqq K\leqq N$、$n[i]\leqq10^3$

yukicoder021

解法

3つ以上のグループにできるので$n[i]$の中で最小、最大を別の単一グループに分け、残りを適当にそれ以外のグループに割り振れば、 最小最大のグループの平均はその値になるので、目的を最大化したことになる。

計算量:$O(N)$

ソース

    #include <bits/stdc++.h>
    using namespace std;
    
    using VS = vector<string>;    using LL = long long;
    using VI = vector<int>;       using VVI = vector<VI>;
    #define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
    const int INF = 1e9;                          const LL LINF = 1e16;
    int DX[8] = { 0, 0, 1, -1, 1, 1, -1, -1 };    int DY[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };
    
    LL N;
    
    LL ans = 0LL;
    
    int main() {
        cin.tie(0);
        ios_base::sync_with_stdio(false);
    
        int K; cin >> N >> K;
        VI a(N);
        int M = -INF, m = INF;
        FOR(i, 0, N) {
            int a; cin >> a;
            M = max(M, a);
            m = min(m, a);
        }
        ans = M - m;
        cout << ans << "\n";
    
        return 0;
    }