C++でk個のサブリストの最小最大合計を見つけるプログラム

numsと呼ばれる数値のリストと別の値kがあるとします。リストを空でないk個のサブリストに分割できます。 k個のサブリストの最小最大合計を見つける必要があります。

したがって、入力がnums =[2、4、3、5、12] k =2のような場合、リストを[2、4、3、5]と[のように分割できるため、出力は14になります。 12]。

これを解決するには、次の手順に従います-

• 関数ok（）を定義します。これは、配列v、k、x、

  を取ります。

• cnt：=0、sum：=0

• vの各要素iについて-

  • sum + i> xの場合、-

    • 合計：=i

    • （cntを1増やします）

  • それ以外の場合

    • 合計：=合計+ i

• cnt <=kの場合はtrueを返し、それ以外の場合はfalse

  を返します。

• メインの方法から、次のようにします-

• 低：=0、ret：=0、高：=0

• numsの各要素iについて

  • 高：=高+ i

  • ret：=ret + i

  • low：=lowとiの最大値

• 低い<=高い間、実行-

  • 中：=低+（高-低）/ 2

  • ok（nums、k --1、mid）が真の場合、-

    • ret：=mid

    • 高：=中-1

  • それ以外の場合

    • 低：=中+ 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