问题陈述： Dilpreet 想要粉刷他的狗的家，家里有 n 块不同长度的木板。第 i 个板的长度由 arr[i] 给出，其中 arr[] 是一个包含 n 个整数的数组。他为这项工作雇佣了 k 个油漆工，每个油漆工需要 1 个单位时间来绘制 1 个单位的木板。
问题是找到完成这项工作的最短时间，如果所有油漆工一起开始，并且任何油漆工都只能油漆连续的木板，例如编号为 {2,3,4} 的木板或仅木板 {1} 或什么都没有不是板 {2,4,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;
}
该算法是正确的，但对于大输入，总和可能会超出
intminTimelong longsumOfAlllong long sumlong longfindPainterslong long maxLengthcurrLengthlong longminTimelowhighmidlong long通过这些修复，它应该可以工作。