nums라는 숫자 목록과 다른 값 k가 있다고 가정합니다. 목록을 k개의 비어 있지 않은 하위 목록으로 분할할 수 있습니다. k 하위 목록의 최소 최대 합을 찾아야 합니다.
따라서 입력이 nums =[2, 4, 3, 5, 12] k =2와 같으면 [2, 4, 3, 5] 및 [ 12].
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
ok() 함수를 정의하면 배열 v, k, x,
가 사용됩니다. -
cnt :=0, 합계 :=0
-
v −
의 각 요소 i에 대해-
합계 + i> x이면 -
-
합계 :=나는
-
(cnt를 1씩 증가)
-
-
그렇지 않으면
-
합계 :=합계 + i
-
-
-
cnt <=k이면 true를 반환하고, 그렇지 않으면 false
를 반환합니다. -
주요 방법에서 다음을 수행하십시오 -
-
낮음 :=0, ret :=0, 높음 :=0
-
숫자의 각 요소 i에 대해
-
높음 :=높음 + i
-
렛 :=렛 + i
-
낮음 :=낮음 및 i의 최대값
-
-
낮음 <=높음, 수행 -
-
중간 :=낮음 + (높음 - 낮음) / 2
-
ok(nums, k - 1, mid)가 참이면 -
-
ret :=중간
-
높음 :=중간 - 1
-
-
그렇지 않으면
-
낮음 :=중간 + 1
-
-
-
리턴 렛
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
#include <bits/stdc++.h>
using namespace std;
bool ok(vector <int>& v, int k, int x){
int cnt = 0;
int sum = 0;
for(int i : v){
if(sum + i > x){
sum = i;
cnt++;
}
else{
sum += i;
}
}
return cnt <= k;
}
int solve(vector<int>& nums, int k) {
int low = 0;
int ret = 0;
int high = 0;
for(int i : nums){
high += i;
ret += i;
low = max(low, i);
}
while(low <= high){
int mid = low + ( high - low) / 2;
if(ok(nums, k - 1, mid)){
ret = mid;
high = mid - 1;
}
else{
low = mid + 1;
}
}
return ret;
}
int main(){
vector<int> v = {2, 4, 3, 5, 12};
int k = 2;
cout << solve(v, k);
} 입력
{2, 4, 3, 5, 12}, 2 출력
14