จัดสรรหน้าหนังสือให้นักเรียนน้อยที่สุด (Allocate Minimum Pages) ใน C++

บทนำ

โจทย์: กำหนดจำนวนหน้าของหนังสือ n เล่ม (เรียงจากน้อยไปมาก) และ m นักเรียน ต้องจัดสรรหนังสือติดต่อกันให้แต่ละนักเรียน โดยต้องการให้ จำนวนหน้าสูงสุดที่นักเรียนคนใดคนหนึ่งต้องอ่าน น้อยที่สุด

ตัวอย่าง

books[] = {13, 43, 65, 87, 92}, m = 2 → Output: 179

การวิเคราะห์กรณี (m=2)

• [13] , [43,65,87,92] → max = 287
• [13,43] , [65,87,92] → max = 244
• [13,43,65] , [87,92] → max = 179 ← คำตอบ
• [13,43,65,87] , [92] → max = 208

แนวคิด: Binary Search

1. ตั้งค่า low = 0, high = sum ของทุกหน้า
2. mid = (low+high)/2 → ตรวจสอบว่าจัดสรรได้หรือไม่ด้วย max pages = mid
3. ถ้าได้ → ลด high = mid-1, บันทึกคำตอบ
4. ถ้าไม่ได้ → เพิ่ม low = mid+1

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

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

bool isPossible(int arr[], int n, int m, int curr_min) {
    int studentsRequired = 1, curr_sum = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] > curr_min) return false;
        if (curr_sum + arr[i] > curr_min) {
            studentsRequired++;
            curr_sum = arr[i];
            if (studentsRequired > m) return false;
        } else curr_sum += arr[i];
    }
    return true;
}

int min_pages(int arr[], int n, int m) {
    long long sum = 0;
    if (n < m) return -1;
    for (int i = 0; i < n; i++) sum += arr[i];
    
    int minimum = 0, maximum = sum, result = INT_MAX;
    while (minimum <= maximum) {
        int mid = (minimum + maximum) / 2;
        if (isPossible(arr, n, m, mid)) {
            result = min(result, mid);
            maximum = mid - 1;
        } else minimum = mid + 1;
    }
    return result;
}

int main() {
    int n = 5;
    int books[] = {13, 43, 65, 87, 92};
    int m = 2;
    cout << "Minimum number of pages = " << min_pages(books, n, m);
    return 0;
}

ผลลัพธ์

Minimum number of pages = 179