Question

Please write code in C++ and comment out code

Question:

We have to paint n boards of length {A1, A2, .. An}. There are k painters available and each takes 1 unit time to paint 1 unit of board. The problem is to find the minimum time to get this job done under the constraints that any painter will only paint continuous sections of boards, say board {2, 3, 4} or only board {1} or nothing but not board {2, 4, 5}.

Examples :

Input : k = 2, A = {10, 10, 10, 10}

Output : 20.

Here we can divide the boards into 2

equal sized partitions, so each painter

gets 20 units of board and the total

time taken is 20.

Input : k = 2, A = {10, 20, 30, 40}

Output : 60.

Here we can divide first 3 boards for

one painter and the last board for

second painter.

Answer 1

#include<iostream>
using namespace std;

int sumBetween2Points(int i, int j, int arr[]){
int total =0;
for(int k=i;k<=j;k++){
total = total + arr[k];
}
return k;
}

int arrayDivision(int n, int arr[],k){
int best = INT_MAX;

if(k==1){
sumBetween2Points(0,n,arr);
}

if(n==1){
return arr[0];
}

for(int i=1;i<=n;i++){
best = min(best,max(arrayDivision(i,arr,k-1),sumBetween2Points(i,n-1,arr)));
}

return best;

}

int main(){
int arr[] = {10,20,30,40};
int n = sizeof(arr);
int k =2;
cout << arrayDivision(n,arr,k);
return 0;
}