Hiểu bài toán

Xét một dãy số $A$ gồm $N$ phần tử. Ban đầu ta có một tổng $S$ bằng tổng các phần tử của $A$. Tại mỗi bước, ta có thể chọn một cặp chỉ số $(i, j)$ với $i \neq j$, xóa $A[i]$ và $A[j]$ khỏi dãy, và thêm vào tổng $S$ giá trị $\max(0, A[i] - A[j])$. Quá trình này lặp lại cho đến khi dãy $A$ chỉ còn lại một phần tử (hoặc rỗng). Nhiệm vụ của bạn là tìm giá trị tổng $S$ lớn nhất có thể đạt được sau khi thực hiện các thao tác này.

Các cách tiếp cận

Cách Giả lập trực tiếp

#include <bits/stdc++.h>
using namespace std;

int main() {
    freopen("cachnhiet.inp", "r", stdin);
    freopen("cachnhiet.out", "w", stdout);
    int n;
    cin >> n;
    vector<long long> a(n);
    long long sum = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        sum += a[i];
    }
    // Sắp xếp mảng để dễ thao tác
    sort(a.begin(), a.end());

    // Mô phỏng quá trình: luôn ghép phần tử lớn nhất với phần tử nhỏ nhất
    while (a.size() > 1) {
        long long x = a.back(); a.pop_back();
        long long y = a.front(); a.erase(a.begin());
        if (x > y) {
            sum += (x - y);
        }
        // Nếu x <= y, ta có thể chọn 2 phần tử khác để tạo giá trị dương,
        // nhưng với cách chọn max-min này, ta đảm bảo tối ưu.
        // Tuy nhiên, logic thực sự cần xử lý mảng còn lại.
        // Giải pháp gốc đã tối ưu hóa logic này.
    }
    cout << sum << endl;
    return 0;
}

• Time Complexity: O(N^2)
• Space Complexity: O(N)

Cách tiếp cận này mô phỏng chính xác quá trình được mô tả. Tuy nhiên, việc xóa phần tử đầu và cuối mảng (hoặc tìm cặp tối ưu) trong một vector liên tục là chậm. Nếu ta thử tất cả các cặp có thể, độ phức tạp sẽ cao. Tuy nhiên, các giải pháp trong bài nộp cho thấy một mô hình tối ưu hơn mà không cần mô phỏng từng bước một cách chậm chạp. Cách này không hiệu quả và không được dùng trong các giải pháp đã cho, nhưng nó minh họa cho suy nghĩ ban đầu.

Cách Sắp xếp và Tính toán trực tiếp (Optimal)

#include <bits/stdc++.h>
using namespace std;

int main() {
    freopen("cachnhiet.inp", "r", stdin);
    freopen("cachnhiet.out", "w", stdout);
    long long n, tong = 0;
    cin >> n;
    vector<long long> a(n);
    for (long long i = 0; i < n; i++) {
        cin >> a[i];
        tong += a[i];
    }
    // Sắp xếp mảng tăng dần
    sort(a.begin(), a.end());

    // Sử dụng kỹ thuật hai con trỏ hoặc duyệt từ ngoài vào trong
    // Để tính tổng hiệu giữa các cặp tối ưu
    long long l = 0, r = n - 1;
    while (l <= r) {
        // Nếu n chẵn, ta sẽ có n/2 cặp hiệu. Nếu n lẻ, có (n-1)/2 cặp hiệu,
        // phần tử ở giữa (l=r) sẽ được cộng 0 (do max(0, a[r]-a[l]))
        tong += max((long long)0, a[r] - a[l]);
        l++;
        r--;
    }
    cout << tong;
    return 0;
}

• Time Complexity: O(N log N)
• Space Complexity: O(N)

Đây là giải pháp tối ưu đã được chứng minh qua các bài nộp.

1. Tổng ban đầu: Tính tổng $S$ ban đầu của các phần tử.
2. Sắp xếp: Sắp xếp mảng $A$ tăng dần.
3. Tối ưu hóa: Để đạt được tổng lớn nhất, ta luôn muốn giá trị thêm vào $\max(0, A[i] - A[j])$ là lớn nhất. Điều này có nghĩa ta nên chọn $A[i]$ là phần tử lớn nhất và $A[j]$ là phần tử nhỏ nhất của mảng còn lại.
   • Khi ta chọn cặp $(A{min}, A{max})$, ta được cộng thêm $A{max} - A{min}$.
   • Sau đó, ta loại bỏ hai phần tử này và tiếp tục với mảng còn lại.
   • Nếu mảng có số lượng phần tử lẻ, phần tử ở giữa sẽ không tạo ra hiệu dương với bất kỳ phần tử nào nếu ta áp dụng logic tương tự (hoặc nó được giữ lại cuối cùng).
   • Thực chất, hiệu quả của thao tác này tương đương với việc tính tổng các hiệu $A{right} - A{left}$ cho các cặp đối xứng từ ngoài vào trong.
4. Công thức: Tổng cuối cùng = Tổng ban đầu + $\sum \max(0, A{n-1-i} - Ai)$ với $i$ chạy từ $0$ đến $\lfloor \frac{n-1}{2} \rfloor$.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán có tính đối xứng: Vị trí của các phần tử không quan trọng, chỉ quan trọng đến giá trị của chúng.
• Chiến lược tối ưu là luôn ghép phần tử lớn nhất với phần tử nhỏ nhất để tạo ra hiệu dương lớn nhất có thể.
• Quá trình 'lấy ra và thêm vào' có thể được tính toán trực tiếp bằng cách sắp xếp và so sánh các cặp đối xứng, thay vì mô phỏng từng bước.

Lỗi thường gặp

• Quên dùng kiểu dữ liệu long long cho biến tổng và mảng, dẫn đến tràn số (overflow) vì giá trị có thể lên tới $10^{14}$.
• Lỗi truy cập mảng khi mảng có độ dài lẻ: Cần đảm bảo vòng lặp chỉ chạy đúng số lần cần thiết (vd: l <= r hoặc i < n/2).
• Không xử lý đúng trường hợp $A[i] \le A[j]$ (hiệu âm). Đề bài yêu cầu cộng $\max(0, A[i] - A[j])$, nên nếu hiệu âm thì không cộng thêm gì.