資料結構
網路
關係資料庫管理系統 (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
廣告