Spoiler Alert

Approach

• Sort giảm dần, lấy giá trị 2 cuốn rồi bỏ qua 1 cuốn

Đề yêu cầu: Cứ mỗi cặp 3 số mình sẽ lấy số nhỏ nhất bỏ đi, còn lại là tính tổng

Chứng minh: Cứ mỗi cặp \((a, b, c)\) và \((a \geq b \geq c)\) để mình lợi nhất thì \(c\) phải lớn nhất có thể. Mà nếu sắp xếp giảm dần thì mỗi cặp 3 số sẽ có \(c\) thỏa mãn

Question

• Liệu bài này có thể giải bằng quy hoạch động không ?

Reference AC code | \(O(n\) \(log_2n)\) time | \(O(n)\) auxiliary space | Sorting, Greedy

int main()
{
    int n = readInt();

    vi a(n);
    for (int &x : a) cin >> x;
    sort(all(a), greater<int>());

    ll res = 0;
    for (int i = 0; i < n; i += 3)
        res += a[i] + a[i + 1];

    cout << res;
    return 0;
}