提问人:Ashwin Bhargava 提问时间:8/1/2022 更新时间:8/1/2022 访问量:56
为什么“studentRequired < m”在最小分配问题中返回 true
Why "studentRequired < m" returns true in minimum allocation problem
问:
在功能中的书籍分配问题中,为什么即使少于(我们需要为学生分配书籍)的结果也是一个可行的解决方案,而我们?这难道不是说没有把书分配给所有学生吗?isPossible()
studentsRequired
m
curr_min
return true
例如,如果数组带有 .获取的最大值为 13。这难道不是说只有 13 名学生拿到了书,但 16 名学生应该拿到书吗?[5, 82, 52, 66, 16, 37, 38, 44, 1, 97, 71, 28, 37, 58, 77, 97, 94, 4, 9]
m = 16
studentsRequired
这是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
答: 暂无答案
下一个:如何使用集合组合作为测试数据
评论