末世分配资源包[200分]

题目内容

末世时代，政府为各地分配资源，现有资源分配表 nums[n]，要求按如下规则分配给 $k$ 个营地：

• 每个营地只分配一段连续的分配表
• 每个营地至少分到一份资源
• 所有的资源必须全部分出
• 分配方式：尽量平均分配（即：得利最大的营地获得的资源值尽量小）

输入描述

• 资源存储数组 nums[n]（资源数 $n$：$0 \le n \le 1000$，每份资源数：$1 \le nums[i] \le 100000$）
• 营地数 $k$（$1 \le k \le \min(50,n)$）

输出描述

在最优平均分配情况下，得利最大团队所获得的资源数。

样例

样例 1

输入

4,3,6,9,7
2

输出

16

说明： 可能的切分：

• $[4],[3,6,8,9,7]$，最大值：25
• $[4,3],[6,9,7]$，最大值：22
• $[4,3,6],[9,7]$，最大值：16
• $[4,3,6,9],[7]$，最大值：22

因此，最大值最小的切分方式是第 3 种，返回 16。

样例 2

输入

3,4,2,1
4

输出

4

说明： 可能的切分：$[3],[4],[2],[1]$，最大值：4。因此，最大值最小的切分方式是第 1 种，返回 4。

代码

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});
rl.on('line', (input) => {
    const nums = input.split(',').map(Number);
    rl.on('line', (input) => {
        const k = Number(input);
        if (!nums.length || k > nums.length) {
            console.log(0);
        }
        let left = Math.max(...nums);
        let right = nums.reduce((a, b)=>a+b);
        // console.log(left, right)
        while(left < right) {
            const mid = Math.floor((left + right)/2);
            if (canSplit(nums, k, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        console.log(left);
        function canSplit(nums, k, mid) {
            let cur = 0;
            let count = 1;
            for(let i=0; i<nums.length; i++) {
                if (nums[i] > mid) return false;
                if (cur + nums[i] > mid) {
                    count++;
                    cur = nums[i];
                    if (count > k) {
                        return false;
                    }
                } else {
                    cur += nums[i];
                }
            }
            if (count <= k) {
                return true;
            } else {
                return false;
            }
        }
    })
})