Binary serch (page allocation )
user_6075971
plain_text
3 years ago
1.3 kB
8
Indexable
#include <iostream>
using namespace std;
bool check(int arr[], int n, int m, int mid)
{
int student = 1;
int pagesum = 0;
for (int i = 0; i < n; i++)
{
if (pagesum + arr[i] <= mid)
{
pagesum += arr[i];
}
else
{
student++;
if (mid < arr[i] || m <student)
{
return false;
}
pagesum = arr[i];
}
}
return true;
}
int possible_min(int arr[], int n, int m)
{
int sum = 0;
for (int i = 0; i < n; i++)
{
sum += arr[i];
}
int s = 0;
int ans = -1;
int e = sum;
int mid = (s + e) / 2;
while (s <= e)
{
if (check(arr, n, m, mid))
{
ans = mid;
e=mid-1;
}
else
{
s=mid+1;
}
mid = (s + e) / 2;
}
return ans;
}
int main()
{
int n;
int m;
cout << "ENTER THE SIZE OF ARRAY--->";
cin >> n;
int arr[100];
for (int i = 0; i < n; i++)
{
cin >> arr[i];
}
for (int i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
cout<<endl;
cout << "ENTER THE STUDENT COUNT--->";
cin >> m;
cout<<endl;
cout << "ANSWER--->" << possible_min(arr,n,m);
return 0;
Editor is loading...