数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++程序：查找k个子列表的最小最大和
假设我们有一个名为nums的数字列表和另一个值k。我们可以将列表分成k个非空子列表。我们必须找到k个子列表的最小最大和。
因此，如果输入类似于nums = [2, 4, 3, 5, 12] k = 2，则输出将为14，因为我们可以将列表分成：[2, 4, 3, 5]和[12]。
为了解决这个问题，我们将遵循以下步骤：
定义一个函数ok()，它将接收数组v、k、x作为参数。
cnt := 0, sum := 0
对于v中的每个元素i：
如果sum + i > x，则：
sum := i
(cnt加1)
否则
sum := sum + i
如果cnt <= k，则返回true；否则返回false。
在主方法中执行以下操作：
low := 0, ret := 0, high := 0
对于nums中的每个元素i
high := high + i
ret := ret + i
low := max(low, i)
当low <= high时：
mid := low + (high - low) / 2
如果ok(nums, k - 1, mid)为true，则：
ret := mid
high := mid - 1
否则
否则
low := mid + 1
返回ret
示例
#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
更新于：2020年12月23日
浏览量：132
广告