Split Array Min Largest Sum
JavaScript
Hard
5 views
Problem Description
Given array and m, split into m continuous parts so that the largest part sum is minimum. Print that minimum largest sum.
Input Format
Line1: n m. Line2: n integers.
Output Format
One integer answer.
Official Solution
const fs=require('fs');const raw=fs.readFileSync(0,'utf8').trim();if(!raw)process.exit(0);const a=raw.split(/\\s+/);let i=0;const n=Number(a[i++]);const m=Number(a[i++]);let arr=new Array(n);let lo=0n,hi=0n;for(let j=0;j<n;j++){const v=BigInt(a[i++]);arr[j]=v;if(v>lo)lo=v;hi+=v;}const can=mid=>{let parts=1;let sum=0n;for(const v of arr){if(sum+v>mid){parts++;sum=v;if(parts>m)return false;}else sum+=v;}return true;};while(lo<hi){const mid=(lo+hi)/2n;if(can(mid))hi=mid;else lo=mid+1n;}process.stdout.write(lo.toString());
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!