최소 페이지 수를 할당하는 것은 프로그래밍 문제입니다. 이 문제에 대해 자세히 논의하고 이에 대한 해결책이 무엇인지 살펴보겠습니다.
명세서
n개의 서로 다른 책의 페이지 수가 제공됩니다. . 또한 m명의 학생이 있습니다. 책을 할당받을 사람. 책은 페이지 수의 오름차순으로 정렬됩니다. 그리고 모든 학생에게 연속된 책을 할당할 수 있습니다. 프로그램은 학생이 읽을 수 있는 최소 페이지 수를 반환해야 합니다.
이 문제를 더 잘 이해하기 위해 예를 들어 보겠습니다.
Input : books[] = {13 , 43, 65, 87, 92}
m = 2
Output : 179 설명
이 문제에는 책을 읽고 있는 두 명의 학생이 있습니다. 따라서 그들 사이에 책을 배포하는 방법은 다음과 같습니다.
사례 1 - [13] , [43, 65, 87, 92 ]
이것은 학생이 읽는 최대 페이지 수를 13/287이 되게 합니다.
사례 2 - [13, 43] , [65, 87,92]
이것은 학생이 읽는 최대 페이지 수를 56/244로 만듭니다.
사례 3 - [13, 43, 65] , [87, 92]
이것은 학생이 읽을 수 있는 최대 페이지 수가 121/179가 되도록 합니다.
사례 4 - [13, 43, 65, 87], [92]
이것은 학생이 읽을 수 있는 최대 페이지 수를 208/92로 만듭니다.
이 4가지 경우 중 결과는 179번입니다.
이 예를 통해 문제가 명확해졌을 것입니다. 이제 그 이면의 논리를 이해하고 이를 위한 프로그램을 작성해 보겠습니다.
이 문제를 해결하기 위해 쉬운 접근 방식은 이진 검색 알고리즘을 사용하는 것입니다. 이 이진 검색 접근 방식의 경우 최소 및 최대 페이지 수를 모든 책의 페이지 합계와 0으로 초기화합니다. 그리고 이 값의 중간값을 중간 결과로 수정하여 알고리즘이 더 진행됨에 따라 변경됩니다.
이제 중간 값을 사용하여 최종 솔루션을 찾을 가능성을 찾으려고 합니다. 현재 mid가 해결책이 될 기회가 있다면, 하반부, 즉 최소에서 mid가 검색됩니다. 이 경우가 사실이 아니면 나머지 절반, 즉 중간에서 최대가 검색됩니다.
이 방법은 이 문제에 대한 해결책을 찾는 데 사용할 수 있지만 학생 수가 증가함에 따라 이 알고리즘은 덜 안정적인 솔루션을 제공하는 경향이 있습니다.
예시
#include<bits/stdc++.h>
using namespace std;
bool isPossible(int arr[], int n, int m, int curr_min) ;
int min_pages(int arr[], int n, int m) ;
int main(){
int n = 5;
int books[] = {13 , 43, 65, 87, 92};
cout<<"The number of page in books are :\n";
for(int i = 0 ; i< n; i++){
cout<<books[i]<<"\t";
}
int m = 2;
cout<<"\nMinimum number of pages = "<<min_pages(books, n, m)<<endl;
return 0;
}
bool isPossible(int arr[], int n, int m, int curr_min){
int studentsRequired = 1;
int curr_sum = 0;
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 min_pages(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 minimum = 0, maximum = sum;
int result = INT_MAX;
while (minimum <= maximum){
int mid = (minimum + maximum) / 2;
if (isPossible(arr, n, m, mid)){
result = min(result, mid);
maximum = mid - 1;
}
else
minimum = mid + 1;
}
return result;
} 출력
The number of page in books are : 13 43 65 87 92 Minimum number of pages = 179