Chương trình tìm tổng lớn nhất nhỏ nhất của k danh sách con trong C ++

Giả sử chúng ta có một danh sách các số được gọi là num và một giá trị khác là k. Chúng ta có thể chia danh sách thành k danh sách con không rỗng. Chúng ta phải tìm tổng lớn nhất nhỏ nhất của k danh sách con.

Vì vậy, nếu đầu vào là nums =[2, 4, 3, 5, 12] k =2, thì đầu ra sẽ là 14, vì chúng ta có thể chia danh sách như:[2, 4, 3, 5] và [ 12].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một hàm ok (), điều này sẽ lấy mảng v, k, x,

• cnt:=0, sum:=0

• cho mỗi phần tử tôi trong v -

  • nếu sum + i> x thì -

    • sum:=i

    • (tăng cnt lên 1)

  • Nếu không

    • sum:=sum + i

• trả về true khi cnt <=k, ngược lại là false

• Từ phương thức chính, hãy làm như sau -

• thấp:=0, ret:=0, cao:=0

• cho mỗi phần tử tôi trong nums

  • high:=high + i

  • ret:=ret + i

  • thấp:=tối đa của thấp và i

• trong khi thấp <=cao, làm -

  • giữa:=low + (cao - thấp) / 2

  • nếu ok (nums, k - 1, mid) là true, thì -

    • ret:=mid

    • cao:=mid - 1

  • Nếu không

    • thấp:=mid + 1

• trả lại ret

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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);
}

Đầu vào

{2, 4, 3, 5, 12}, 2

Đầu ra

14