แจกลูกอมใน C++ (Candy)

ภาพรวมปัญหา

เด็ก N คนเรียงกัน แต่ละคนมี rating ให้ลูกอมตามกติกา:
1. ทุกคนได้อย่างน้อย 1 ลูก
2. Rating สูงกว่าเพื่อนบ้าง → ได้ลูกอมมากกว่าเพื่อนบ้าน

ตัวอย่าง

[1,1,3] → ลูกอม: [1,1,2] → รวม 4

วิธีแก้ปัญหา: Two Pass Greedy

1. Left to right: ถ้า rating[i] > rating[i-1] → dp[i] = dp[i-1] + 1
2. Right to left: ถ้า rating[i] > rating[i+1] → dp[i] = max(dp[i], dp[i+1] + 1)
3. รวม dp ทั้งหมด

โค้ด 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));
}

ผลลัพธ์

4

การวิเคราะห์ความซับซ้อน

• เวลา: O(n)
• พื้นที่: O(n)