Lời giải

Mỗi thao tác cộng ~|a_i - a_{i+1}|~ vào điểm, tức lấy số lớn trừ số nhỏ. Ta có thể coi như số lớn mang dấu cộng và số nhỏ mang dấu trừ. Sau ~n~ thao tác, mỗi phần tử bị xóa đúng một lần, nên có đúng ~n~ phần tử mang dấu cộng và ~n~ phần tử mang dấu trừ. Tổng như vậy lớn nhất khi ~n~ phần tử lớn nhất mang dấu cộng và ~n~ phần tử nhỏ nhất mang dấu trừ. Nếu sắp các phần tử tăng dần thành ~c_1 \le c_2 \le \cdots \le c_{2n}~ thì điểm số không vượt quá

~(c_{n+1} + \cdots + c_{2n}) - (c_1 + \cdots + c_n).~

Ta sẽ chỉ ra rằng luôn đạt được chặn trên này. Gán nhãn ~B~ cho ~n~ phần tử lớn nhất và ~S~ cho ~n~ phần tử nhỏ nhất (nếu có các phần tử bằng nhau ở ranh giới thì chia tùy ý). Khi đó mọi phần tử ~B~ đều lớn hơn hoặc bằng mọi phần tử ~S~.

Ban đầu số phần tử ~B~ bằng số phần tử ~S~. Nếu mảng còn phần tử, chắc chắn có một chỗ một ~B~ đứng cạnh một ~S~, vì nếu không thì cả mảng cùng một nhãn, trái với việc số ~B~ bằng số ~S~. Ta xóa cặp đó và được đúng ~b - s~ điểm: phần tử ~B~ được cộng, phần tử ~S~ bị trừ, đúng như mong muốn. Sau khi xóa, số ~B~ vẫn bằng số ~S~, nên ta lặp lại được cho đến khi mảng rỗng. Tổng điểm thu được đúng bằng chặn trên.

Như vậy điều kiện chỉ được xóa hai phần tử kề nhau không làm giảm đáp án. Ta chỉ cần sắp xếp mảng rồi lấy tổng ~n~ phần tử lớn trừ tổng ~n~ phần tử nhỏ. Ở bộ test thứ ba trong đề, ~n~ phần tử lớn là ~4, 5, 6~ và ~n~ phần tử nhỏ là ~1, 2, 3~, nên đáp án là ~15 - 6 = 9~.

Chương trình

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;

#ifdef JASPER
#include <debug.h>
#else
#define debug(...) 166
#endif

void solve() {
    int n;
    cin >> n;
    vector<ll> a(2 * n);
    for (auto &x : a) cin >> x;
    sort(a.begin(), a.end());
    ll ans = 0;
    for (int i = 0; i < n; ++i) ans += a[n + i] - a[i];
    cout << ans << "\n";
}

signed main() {
    cin.tie(0) -> sync_with_stdio(0);

    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }

    return 0;
}

Độ phức tạp là ~O(n \log n)~ cho mỗi bộ test. Có thể hạ xuống ~O(n)~ bằng nth_element, nhưng không cần thiết. Trên test nặng nhất (~n = 2 \cdot 10^5~, tức ~4 \cdot 10^5~ số), chương trình chạy trong 0,03 s và dùng 12 MB, trong khi giới hạn là ~2~ s và ~256~ MB.

Lỗi thường gặp

• Nếu mỗi lần đều xóa cặp kề có hiệu lớn nhất thì kết quả sai. Với ~[3, 1, 4, 10, 2, 8]~, cách này được ~8 + 4 + 2 = 14~, còn đáp án là ~(10 + 8 + 4) - (1 + 2 + 3) = 16~.
• Quy hoạch động trên đoạn cho kết quả đúng nhưng chạy ~O(n^3)~, chỉ qua được vài test nhỏ. Khi ~n~ lên tới ~2 \cdot 10^5~ mà đề vẫn nhấn mạnh điều kiện "kề nhau", nên thử kiểm tra xem điều kiện đó có thật sự ảnh hưởng đến đáp án hay không.
• Đáp án có thể lên tới ~2 \cdot 10^{14}~, nên phải dùng long long.
• Mỗi bộ test có ~2n~ số, không phải ~n~.