为什么“studentRequired < m”在最小分配问题中返回 true

Why "studentRequired < m" returns true in minimum allocation problem

提问人:Ashwin Bhargava 提问时间:8/1/2022 更新时间:8/1/2022 访问量:56

问:

在功能中的书籍分配问题中,为什么即使少于(我们需要为学生分配书籍)的结果也是一个可行的解决方案,而我们?这难道不是说没有把书分配给所有学生吗?isPossible()studentsRequiredmcurr_minreturn true

例如,如果数组带有 .获取的最大值为 13。这难道不是说只有 13 名学生拿到了书,但 16 名学生应该拿到书吗?[5, 82, 52, 66, 16, 37, 38, 44, 1, 97, 71, 28, 37, 58, 77, 97, 94, 4, 9]m = 16studentsRequired

这是JS中的代码,对于其他语言(cpp,java,python),请访问此GFG页面

function isPossible(arr, n, m, curr_min) {
    let studentsRequired = 1;
    let curr_sum = 0;
    for (let 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;
}
function findPages(arr, n, m) {
    let sum = 0;
    if (n < m) return -1;
    for (let i = 0; i < n; i++) sum += arr[i];
    let start = 0,
        end = sum;
    let result = Number.MAX_VALUE;
    while (start <= end) {
        let mid = Math.floor((start + end) / 2);
        if (isPossible(arr, n, m, mid)) {
            result = Math.min(result, mid);
            end = mid - 1;
        } else start = mid + 1;
    }
    return result;
}

const ans = findPages(
    [5, 82, 52, 66, 16, 37, 38, 44, 1, 97, 71, 28, 37, 58, 77, 97, 94, 4, 9],
    19,
    16
);
console.log("Ans : ", ans);

我认为正在发生的事情=>
当我用 试运行测试用例的代码时,结果是 S1 = [10,20],S2 = [30],S3 = [40],我们没有为 S4 分配一本书。
我们是否假设拥有更多书籍的学生(如 S1 有 [10,20])可以转移到最后一本书,在这种情况下是 20 到那里合适的学生?然后 S2 将有 [20,30],所以 30 将被转移到 S3,最后 S3 会将其最后一本书转移到 S4,使条件“每个学生都必须有一本书”为真,就像现在 S1 = [10]、S = [20]、S3 = [30]、S4 = [40]?还是别的什么?
arr = [10,20,30,40]m = 4

算法 与语言无关 的二进制搜索

评论


答: 暂无答案