分配书籍 DSA 问题 - 当分配给较少学生的书籍时，为什么需要存储答案？

Question

对于 DSA 问题 - 分配书籍，以下解决方案对于少数测试用例失败。当

if(students==m)

行被删除时，所有测试用例都会通过。但这没有意义，为什么当

numberOfStudents(mid,arr,m)

返回的数字小于要求的学生时我们要存储答案。问题提到所有学生都需要分配书本。

public class Solution {

    public static int findPages(ArrayList<Integer> arr, int n, int m) {
        
        if(arr.size()<m) return -1;

        return BinarySearchSolution(arr,m,m);

    }
 

    public static int BinarySearchSolution(ArrayList<Integer> arr, int n, int m){

        int max = -1;
        int sum= 0;

        for(int i:arr){
            max = Math.max(i,max);
            sum+=i;
        } 
        
        int low = max,high=sum;
        int ans=Integer.MAX_VALUE;
        while(low<=high){

            int mid =(low + high) /2;
        
           int students = numberOfStudents(mid,arr,m);
            if(students<=m){
                high=mid-1;
                if(students==m) ans=mid;  
            }else{
                low = mid+1;
            }

        }

        return ans;

    }


    public static int numberOfStudents(int limit,ArrayList<Integer> arr, int m){

        int currentPagesSum = 0;
        int students = 0;

        for(int i=0;i<arr.size();i++){
            if(arr.get(i) + currentPagesSum <=limit  ){
                currentPagesSum +=arr.get(i);
            }else{
                students++;
                currentPagesSum=0;
                i--;
            }
        }
        return students+1;
    }


}

Answer 1

下面的博客完美地解释了该解决方案为何有效。

https://medium.com/@bharathurs42/allocate-books-69a87f7ee9e6#:~:text=This%20works%20%E2%80%94%20but%20I%20was%20wondering%20why%20this%20part% 20作品%3A