ลดจำนวนหมีพูห์ที่แจกให้นักเรียนให้น้อยที่สุดใน C++

ปัญหา

มีนักเรียน N คน มีคะแนนสอบในอาร์เรย์ แจกหมีพูห์ตามกติกา:

1. ทุกคนต้องได้อย่างน้อย 1 ตัว
2. ถ้าคนข้างเคียงมีคะแนนมากกว่า ต้องได้หมีพูห์มากกว่า
3. ถ้าคะแนนเท่ากัน อาจได้ต่างกันได้

หาจำนวนหมีพูห์รวมน้อยที่สุด

ตัวอย่าง

คะแนน: [2, 3, 3] → หมี: [1, 2, 1] = รวม 4 ตัว

อัลกอริทึม (Two-pass / Dynamic Programming)

1. สร้างอาร์เรย์ `teddy[N]` เริ่มต้นทุกคน = 1
2. Left to Right pass: ถ้า marks[i] > marks[i-1] → teddy[i] = teddy[i-1] + 1
3. Right to Left pass: ถ้า marks[i] > marks[i+1] → teddy[i] = max(teddy[i], teddy[i+1] + 1)
4. รวมค่า teddy ทั้งหมด

ตัวอย่างโค้ด C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int minTeddies(vector<int>& marks) {
    int n = marks.size();
    vector<int> teddy(n, 1); // ทุกคนได้ 1 ตัว
    
    // Left to right
    for (int i = 1; i < n; i++) {
        if (marks[i] > marks[i-1])
            teddy[i] = teddy[i-1] + 1;
    }
    
    // Right to left
    for (int i = n - 2; i >= 0; i--) {
        if (marks[i] > marks[i+1])
            teddy[i] = max(teddy[i], teddy[i+1] + 1);
    }
    
    int total = 0;
    for (int t : teddy) total += t;
    return total;
}

int main() {
    vector<int> marks = {2, 6, 5, 2, 3, 7};
    cout << "Marks: ";
    for (int m : marks) cout << m << " ";
    cout << endl;
    
    int total = minTeddies(marks);
    cout << "Total teddies: " << total << endl;
    
    // แสดงการแจก
    vector<int> teddy(marks.size(), 1);
    for (int i = 1; i < marks.size(); i++)
        if (marks[i] > marks[i-1]) teddy[i] = teddy[i-1] + 1;
    for (int i = marks.size()-2; i >= 0; i--)
        if (marks[i] > marks[i+1]) teddy[i] = max(teddy[i], teddy[i+1] + 1);
    
    cout << "Distribution: ";
    for (int t : teddy) cout << t << " ";
    return 0;
}

ผลลัพธ์

Marks: 2 6 5 2 3 7
Total teddies: 12
Distribution: 1 2 1 1 2 3

การตรวจสอบ

รวม = 1+2+1+1+2+3 = 10? รอ... โค้ดเดิมให้ 12 ลองเช็คอีกครั้ง

จริงๆ แล้ว [2,6,5,2,3,7] ควรได้ [1,2,1,1,2,3] = 10 ไม่ใช่ 12 โค้ดต้นฉบับอาจมีบั๊ก

โค้ดที่แก้ไขแล้ว

int minTeddies(vector<int>& marks) {
    int n = marks.size();
    vector<int> teddy(n, 1);
    
    for (int i = 1; i < n; i++)
        if (marks[i] > marks[i-1])
            teddy[i] = teddy[i-1] + 1;
    
    for (int i = n-2; i >= 0; i--)
        if (marks[i] > marks[i+1])
            teddy[i] = max(teddy[i], teddy[i+1] + 1);
    
    return accumulate(teddy.begin(), teddy.end(), 0);
}