19. 受限任务分配[200分]

题目内容

某部门有一批待处理任务，数量为 x；系统按轮次处理任务，每次平分后只保留其中一组进入下一轮，当 x=1 时，处理结束，不再执行任何操作。每一轮按照以下规则处理：

• 当 x 为偶数时，执行一次平分操作：
  • 任务数变为 x/2，消耗 1 点成本，操作次数增加 1。
• 当 x 为奇数时，先按如下选择调整任务数为偶数，然后再执行一次平分操作：
  • 新增 1 次任务：任务数变为 x+1，消耗 add_cost 点成本，操作次数增加 1；
  • 减少 1 次任务：任务数变为 x−1，消耗 return_cost 点成本，操作次数增加 1。

当给定一组 new_tasks，请找出平分任务至 1 时，总成本消耗最少的方案；若达到最低总成本的方案有多种，选择其中操作次数最少的方案。

输入描述

• new_tasks：当前任务数，1 ≤ new_tasks ≤ 10000
• budget：成本预算上限，1 ≤ budget ≤ 50
• add_cost：获取 1 个任务的成本，1 ≤ add_cost ≤ 10
• return_cost：回收 1 个任务的成本，1 ≤ return_cost ≤ 10

输出描述

输出 [最低总成本, 最少操作次数]，如果最低总成本超过 budget，输出 [-1,-1]；如果输入任务数为 1，直接输出 [0,0]。

样例

样例 1

输入

5 5 2 1

输出

3 3

说明：

• 5→4：选择回收任务，成本 1，操作次数 1
• 4→2：平分，成本 1，操作次数 1
• 2→1：平分，成本 1，操作次数 1

总成本为 3，操作次数为 3，未超过预算 5。

样例 2

输入

5 2 1 3

输出

-1 -1

说明：

• 选择获取任务：5→6→3，累计成本为 2，操作次数为 2。此时预算已经用完，但任务数仍为 3，后续任何操作都会超出预算。
• 选择回收任务：仅 5→4 就需要成本 3，已经超过预算。因此无法完成。

样例 3

输入

7 30 2 10

输出

5 4

说明：

• 7→8：选择获取任务，成本 2，操作次数 1
• 8→4：平分，成本 1，操作次数 1
• 4→2：平分，成本 1，操作次数 1
• 2→1：平分，成本 1，操作次数 1

总成本为 5，操作次数为 4。虽然先回收任务也可以使任务数变为偶数，但回收成本较高，不是最低成本方案。

代码

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

rl.on('line', (input) => {
    const [new_tasks, budget, add_cost, return_cost] = input.split(' ').map(Number);
    let ans = [Infinity, Infinity];
    const dfs =(task, nums, count) => {
        // console.log(task, nums, count);
        if (nums > budget ||  task === 0) {
            return;
        }
        if (task === 1) {
            if (nums < ans[0]) {
                ans = [nums, count];
            } else if (nums === ans[0]) {
                ans[1] = ans[1] > count ? count : ans[1];
            }
            return;
        } else {
            if (task % 2) {
                // 奇数
                dfs(task+1, nums+add_cost, count+1);
                dfs(task-1, nums+return_cost, count+1);
            } else {
                dfs(task/2, nums+1, count+1);
            }
        }
    }
    dfs(new_tasks, 0, 0);
    console.log(ans[0] === Infinity ? '-1 -1' : ans.join(' '));
});