forked from codingCapricorn/Hactoberfest-2020-native
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathCreate Allocate minimum number of pages
110 lines (97 loc) · 3.09 KB
/
Create Allocate minimum number of pages
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
QUESTION
You are given N number of books. Every ith book has Pi number of pages.
You have to allocate books to M number of students. There can be many ways or permutations to do so. In each permutation one of the M students will be allocated the maximum number of pages. Out of all these permutations, the task is to find that particular permutation in which the maximum number of pages allocated to a student is minimum of those in all the other permutations, and print this minimum value.
Each book will be allocated to exactly one student. Each student has to be allocated atleast one book.
Note: Return -1 if a valid assignment is not possible, and allotment should be in contiguous order (see explanation for better understanding).
Input:
The first line contains 'T' denoting the number of testcases. Then follows description of T testcases:Each case begins with a single positive integer N denoting the number of books.The second line contains N space separated positive integers denoting the pages of each book.And the third line contains another integer M, denoting the number of students.
Output:
For each test case, output a single line containing minimum number of pages each student has to read for corresponding test case.
Expected Time Complexity: O(NLogN).
Expected Auxiliary Space: O(1).
Constraints:
1 <= T <= 100
1 <= N <= 106
1 <= A [ i ] <= 106
1 <= M <= 106
Example:
Input:
2
4
12 34 67 90
2
3
15 17 20
2
Output:
113
32
Explaination:
Testcase 1:Allocation can be done in following ways:
{12} and {34, 67, 90} Maximum Pages = 191
{12, 34} and {67, 90} Maximum Pages = 157
{12, 34, 67} and {90} Maximum Pages = 113
Therefore, the minimum of these cases is 113, which is selected as output.
Testcase 2: Allocation can be done in following ways:
{15} and {17, 20} Maximum pages = 37
{15, 17} and {20} Maximum Pages = 32
So, the output will be 32.
CODE IN C++
#include <bits/stdc++.h>
using namespace std;
bool isPossible(long arr[], long n, long m, long curr_min)
{
long studentsRequired = 1;
long curr_sum = 0;
for (long 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;
}
long findPages(long arr[], long n, long m)
{
long long sum = 0;
if (n < m)
return -1;
for (long i = 0; i < n; i++)
sum += arr[i];
long start = 0, end = sum;
long result = INT_MAX;
while (start <= end)
{
long 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() {
long t,n,m;
cin>>t;
while(t--){
cin>>n;
long arr[n];
for(long i=0;i<n;i++){
cin>>arr[i];
}
cin>>m;
cout <<findPages(arr, n, m) << endl;
}
return 0;
}