程序在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

以上是 程序在C ++中查找k个子列表的最小最大和 的全部内容, 来源链接: utcz.com/z/330760.html

回到顶部