Lời giải

• Dùng thuật toán tham lam:
  • Sắp xếp dãy số ~a_1, a_2, ..., a_N~ theo chiều tăng dần.
  • Độ cách nhiệt lớn nhất của cả khối là ~S = a_1 + a_2 + ... + a_N + max(0, a_N - a_1) + max(0, a_{N - 1} + a_2) + ... + max(0, a_{N - i + 1} - a_i)~ ~(1 \le i \le \frac{N}{2})~.

Code tham khảo

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5 + 2;

int a[MAXN];

void Input(int &n) {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
}

int Solution(int n) {
    int sum = 0;
    sort(a, a + n);
    for (int i = 0; i < n; i++) sum += a[i];
    for (int i = 0; i < n / 2; i++) sum +=  a[n - i - 1] - a[i];
    return sum;    
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    Input(n);

    int sum = Solution(n);
    cout << sum;
    return 0;
}