程序在C ++中查找k个子列表的最小最大和

假设我们有一个称为nums的数字列表，另一个值为k。我们可以将列表分为k个非空子列表。我们必须找到k个子列表的最小最大和。

因此，如果输入像nums = [2、4、3、5、12] k = 2，则输出将是14，因为我们可以像[2、4、3、5]和[ 12]。

在线示例

让我们看下面的实现以更好地理解-

#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