Phân kẹo (Candy) trong C++

N trẻ đứng hàng, mỗi trẻ có rating. Phân kẹo thoả mãn:

1. Mỗi trẻ ≥ 1 viên.
2. Trẻ rating cao hơn hàng xóm → kẹo nhiều hơn hàng xóm đó.

Tìm tổng kẹo tối thiểu.

Ví dụ

ratings = [1,1,3] → Phân: [1, 1, 2] → Tổng = 4.

Thuật toán: 2 lần duyệt (Two-pass Greedy)

1. Khởi tạo dp[i] = 1 cho tất cả.
2. Duyệt trái→phải: nếu ratings[i-1] → dp[i] = dp[i-1] + 1.
3. Duyệt phải→trái: nếu ratings[i+1] → dp[i] = max(dp[i], dp[i+1] + 1).
4. Tổng = sum(dp).

Tại sao 2 lần duyệt?

• Lần 1 đảm bảo điều kiện với hàng xóm trái.
• Lần 2 đảm bảo điều kiện với hàng xóm phải, đồng thời giữ điều kiện trái (dùng max).

Cài đặt C++

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

class Solution {
public:
    int candy(vector<int>& ratings) {
        int n = ratings.size();
        vector<int> dp(n, 1);
        for (int i = 1; i < n; i++)
            if (ratings[i] > ratings[i-1]) dp[i] = dp[i-1] + 1;
        for (int i = n-2; i >= 0; i--)
            if (ratings[i] > ratings[i+1]) dp[i] = max(dp[i], dp[i+1] + 1);
        int ret = 0;
        for (int x : dp) ret += x;
        return ret;
    }
};

int main() {
    Solution ob;
    vector<int> v = {1, 1, 3};
    cout << ob.candy(v);
    return 0;
}

Độ phức tạp

• Thời gian: O(n).
• Không gian: O(n) (có thể tối ưu O(1) nhưng phức tạp hơn).

Input / Output

Input:  [1,1,3]
Output: 4