Question Name:Searching 4

#include <iostream>

#include<bits/stdc++.h>
using namespace std;

bool isPossible(int arr[], int n, int m, int curr_min)
{
int studentsRequired = 1;
int curr_sum = 0;

// iterate over all books
for (int i = 0; i < n; i++)
{

if (arr[i] > curr_min)
return false;

if (curr_sum + arr[i] > curr_min)
{

studentsRequired++;

curr_sum = arr[i];

if (studentsRequired > m)
return false;
}

else
curr_sum += arr[i];
}
return true;
}

int findPages(int arr[], int n, int m)
{
long long sum = 0;

if (n < m)
return -1;

for (int i = 0; i < n; i++)
sum += arr[i];

int start = 0, end = sum;
int result = INT_MAX;

while (start <= end)
{

int mid = (start + end) / 2;
if (isPossible(arr, n, m, mid))
{
result = min(result, mid);

end = mid - 1;
}

else

start = mid + 1;
}

return result;
}

int main()
{
int arr[10] ,i,k;
int m;
scanf("%d",&k);
for(i=0;i<k;i++)
{
scanf("%d",&arr[i]);

}
scanf("%d",&m);
cout << "Minimum number of pages = "
<< findPages(arr, k, m) << endl;
return 0;
}

Problem Description

Given number of pages in n different books and m students. The books are arranged in ascending order of number of pages.

Every student is assigned to read some consecutive books. The task is to assign books in such a way that the maximum number of pages assigned to a student is minimum.

Take Number of books, n, number of pages in n books and the number of students, m as input.

 

 

  • Test Case 1

    Input (stdin)

    4
    12 34 67 90
    2
    

    Expected Output

    Minimum number of pages = 113
  • Test Case 2

    Input (stdin)

    6
    30 55 72 98 102 139
    3
    

    Expected Output

    Minimum number of pages = 200

Leave a Reply

Your email address will not be published. Required fields are marked *

Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.

Powered By
CHP Adblock Detector Plugin | Codehelppro