Phân trang sách cho sinh viên với số trang tối thiểu trong C++

Cho n cuốn sách với số trang (đã sắp xếp tăng), m sinh viên. Mỗi sinh viên nhận các cuốn sách liên tiếp. Tìm giá trị nhỏ nhất của số trang tối đa mà một sinh viên phải đọc.

Ví dụ: books={13,43,65,87,92}, m=2 -> Kết quả 179 (chia {13,43,65} và {87,92}, max sum = 179).

Giải pháp: Tìm kiếm nhị phân (Binary Search).

• low = 0, high = tổng tất cả trang.
• mid = (low+high)/2. Kiểm tra xem có thể phân chia với max trang = mid không (hàm isPossible).
• Nếu có -> high = mid-1, cập nhật kết quả. Không -> low = mid+1.

Ví dụ code

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

bool isPossible(int arr[], int n, int m, int curr_min) {
    int students = 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) {
            students++;
            curr_sum = arr[i];
            if (students > m) return false;
        } else curr_sum += arr[i];
    }
    return true;
}

int minPages(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 low = 0, high = sum, result = INT_MAX;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (isPossible(arr, n, m, mid)) {
            result = min(result, mid);
            high = mid - 1;
        } else low = mid + 1;
    }
    return result;
}

int main() {
    int books[] = {13, 43, 65, 87, 92};
    int n = 5, m = 2;
    cout << "So trang toi thieu: " << minPages(books, n, m);
    return 0;
}

Kết quả

So trang toi thieu: 179