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.