画家分区问题大输入时答案错误的原因排查

问题描述 #

Dilpreet想要粉刷他家狗狗的房子，房子有n块不同长度的木板，第i块木板的长度为arr[i]（arr[]是一个包含n个整数的数组）。他雇佣了k名画家，每位画家每单位时间可以粉刷1单位长度的木板。
问题要求在所有画家同时开始工作，且每位画家只能粉刷连续木板的约束下，找出完成全部粉刷工作的最短时间。
任务：完成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;
}

大输入出错的核心原因：整数溢出 #

代码在处理大输入时出错的根本原因是32位int类型的溢出，具体体现在以下关键位置：

• 求和函数sumOfAll的溢出：根据约束条件，n最大为1e5，每个arr[i]最大为1e5，总和最大可达1e10，而32位int的最大值仅约2.1e9，远小于这个数值。用int存储总和会导致溢出，得到错误的负数或乱码值，直接让二分查找的high边界完全错误。
• findPainters中的累加溢出：currLength用int类型，累加过程中如果超过int范围，会溢出，导致currLength+arr[i]<=maxLength的判断逻辑错误，计算出的所需画家数量完全不对，干扰二分查找的方向。
• 二分查找变量的溢出：low、high、mid都用int类型，当high是溢出后的错误值时，mid的计算也会出错，整个二分逻辑彻底混乱，最终返回错误结果。

修复方案 #

将所有涉及木板长度累加、存储最大值、二分边界的变量全部改为long long类型，避免溢出：

1. 修改findMax函数：

long long findMax(int arr[],int n){
    long long maxi=INT_MIN;
    for(int i=0;i<n;i++){
         maxi=max(maxi,(long long)arr[i]); 
    }
    return maxi; 
}

2. 修改sumOfAll函数：

long long sumOfAll(int arr[],int n){
    long long sum=0;
    for(int i=0;i<n;i++){
         sum+=arr[i];
    }
    return sum;
}

3. 修改findPainters函数：

int findPainters(int arr[],int n,long long maxLength){
    long long currLength=0;
    int painters=1;
    for(int i=0;i<n;i++){
        if(currLength+arr[i]<=maxLength){
            currLength+=arr[i];
        }
        else{
            painters++;
            currLength=arr[i];
        }
    }
    return painters;
}

4. 修改minTime函数：

long long minTime(int arr[], int n, int k)
{
    if(k>=n) return findMax(arr,n); 
    long long low=findMax(arr,n);
    long long high=sumOfAll(arr,n);
    while(low<=high){
         long long mid = low + (high - low) / 2;
        int painters=findPainters(arr,n,mid);
        if(painters<=k){
            high=mid-1;
        }
        else{
            low=mid+1;
        }
    }
    return low;
}

内容的提问来源于stack exchange，提问作者Astha Negi