为什么当输入很大时Painter的分区问题答案不正确？

Question

我正在解决 GeeksforGeeks 问题 画家的分区问题-II ：

Dilpreet 想要粉刷他的狗的家，家里有不同长度的

n

板。第 i 个^{板的长度由} arr[i]

 给出，其中 

arr[]

 是由 

n

 整数组成的数组。他为这项工作雇佣了 

k

 油漆工，每个油漆工需要 

1 单位时间来油漆 1 单位的木板。

问题是找到完成这项工作的最短时间，如果所有油漆工一起开始，并且任何油漆工都只能油漆连续的木板，例如编号为

{2,3,4}

的木板或仅木板

{1}

或仅不木板

{2,4,5}

.

你的任务

您的任务是完成函数

minTime()

，该函数以整数 

n

 和 

k

 以及数组 

arr[]

 作为输入，并返回绘制所有分区所需的最短时间。

限制

1 ≤
• n

   ≤ 10

  5
1 ≤
• k

   ≤ 10

  5
1 ≤
• arr[i]

   ≤ 10

  5

我的代码：

    int findMax(int arr[],int n){
        int maxi=INT_MIN;
        for(int i=0;i<n;i++){
             maxi=max(maxi,arr[i]); 
        }
        return maxi; 
    }
    
    int sumOfAll(int arr[],int n){
        int sum=0;
        for(int i=0;i<n;i++){
             sum+=arr[i];
        }
        return sum;
    }
    
    int findPainters(int arr[],int n,int maxLength){
        // maxLength is the max length a painter can paint 
        int currLength=0; // currLength is the current length painted by current painter
        int painters=1; // no. of painters required
        for(int i=0;i<n;i++){
            if(currLength+arr[i]<=maxLength){
                // we can continue with the same painter
                currLength+=arr[i];
            }
            else{
                // currLength+arr[i]>maxLength
                // more painter required
                painters++;
                currLength=arr[i];
            }
        }
        return painters; // no. of painters required given a painter can paint maxLength length of board
    }
    
    long long minTime(int arr[], int n, int k)
    {
        // when no. of painters are more than or equal to no. of boards then 
        //each painter can paint a single board and max time taken to complete the task will 
        // be the maxLength board present in the array
        if(k>=n) return findMax(arr,n); 
        int low=findMax(arr,n); // min board length a painter atleast should be able to paint 
        int high=sumOfAll(arr,n); // max board length a painter could paint
        while(low<=high){
             int mid = low + (high - low) / 2;
            // mid define the max length a painter is able to paint or max Time taken by both painters
            // to complete the task
            // since each painter takes 1 unit time to paint 1 unit of the board. 
            int painters=findPainters(arr,n,mid);
            // while maintaining the maxLength mid , the painter required to paint are 
            if(painters<=k){
                // keep searching for min(maxTime taken)
                high=mid-1;
            }
            else{
                // increase the maxLength/maxTime to decrease the painter
                low=mid+1;
            }
        }
        return low;
    }

200 多个测试用例中的大多数都通过了，但对于一些非常大的输入，我得到了完全不同的结果。可能是什么原因？

Answer 1

该算法是正确的，但对于大输入，总和可能会超出

int

的范围。由于您的函数 

minTime

 的返回类型为 

long long

，因此对所有总和和长度使用相同的数据类型：

• sumOfAll

   应该有 

  long long sum

   并返回 

  long long
• findPainters

   应该有一个 

  long long maxLength

   作为最后一个参数，并且它的 

  currLength

   变量也应该是 

  long long

  。

在
• minTime

   中，变量 

  low

  、

  high

   和 

  mid

   应为 

  long long

  。

通过这些修复，它应该可以工作。