题面描述:

在这个问题中，我们需要计算出一个量子计算机所需的最低算力，以便在给定的时刻内完成所有子任务。任务的算力需求由一个列表表示，且要求在 T 个时刻内完成这些任务，同时在每个时刻调度的多个任务的算力需求总和不能超过量子计算机的最大算力。通过合理安排任务，可以求得最低的算力需求，以确保所有任务在指定时限内完成。

思路：二分

二分最低的算力需求，因为越高的算力，往往可以越快的完成所有任务，所以满足递增性，可以二分。

对于每个算力需求，直接遍历模拟是否满足在T时刻内完成所有任务。

题解

这个问题要求我们找到量子计算机所需的最低算力，以便在给定的 T 个时刻内完成所有子任务。由于较高的算力能够更快地完成任务，因此可以利用二分查找来优化我们的搜索过程。

思路

1. 定义问题：

   • 给定一个任务的算力需求列表 tasks 和时刻限制 T，我们需要找出最小的算力值 S，使得在 T 个时刻内可以完成所有任务。

2. 二分查找：

   • 将算力需求的范围设定为 [1, 10^9]（可根据实际情况调整）。因为任何有效的算力需求都应该在这个范围内。
   • 利用二分查找法，不断缩小查找范围，以找到最小的满足条件的算力。

3. 模拟检查：

   • 对于每一个猜测的算力 y，遍历任务列表并模拟如何在 T 个时刻内安排任务。
   • 如果当前的算力总和超出 y，则需要增加一个时刻，并重置当前算力。
   • 如果在模拟结束时使用的时刻超过 T，则说明该算力不足。

4. 结果输出：

   • 最终找到的 l 即为所需的最低算力。

JavaScript

// 读取输入，并将其拆分为字符串数组
let input = readline().split(' ');
// 将输入的第一个值转换为整数 N，表示任务数量
let N = parseInt(input[0]);
// 将输入的第二个值转换为整数 T，表示可用的时刻数
let T = parseInt(input[1]);
// 读取任务的算力需求，并将其转换为数字数组 a
let a = readline().split(' ').map(Number);

// 初始化二分查找的左右边界
let l = 1; // 最小算力
let r = 1e9; // 最大算力

// 定义检查函数 check(y)，用于判断当前算力 y 是否能够在 T 时刻内完成所有任务
function check(y) {
    let cur = 0; // 当前时刻内的算力总和
    let res = 1; // 当前使用的时刻数

    // 遍历每个任务的算力需求
    for (let x of a) {
        // 如果当前任务的算力加上当前总和超出 y
        if (cur + x > y) {
            res += 1; // 需要增加一个时刻
            cur = 0; // 重置当前算力总和
        }

        cur += x; // 将当前任务的算力加到当前总和

        // 如果在分配任务时当前算力超过了 y，返回 false
        if (cur > y) {
            return false;
        }
    }

    // 返回使用的时刻数是否小于等于 T
    return res <= T;
}

// 进行二分查找
while (l < r) {
    // 计算中间值
    let mid = (l + r) >> 1;

    // 如果当前算力 mid 能满足条件
    if (check(mid)) {
        r = mid; // 尝试更小的算力
    } else {
        l = mid + 1; // 否则，增加算力
    }
}

// 输出找到的最低算力
print(l);

Java

import java.util.Scanner; // 导入 Scanner 类用于输入处理

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in); // 创建 Scanner 对象以接收输入

        // 读取任务数量 N 和可用的时刻数 T
        int N = scanner.nextInt();
        int T = scanner.nextInt();

        // 创建数组 a 存储每个任务的算力需求
        int[] a = new int[N];
        for (int i = 0; i < N; i++) {
            a[i] = scanner.nextInt(); // 读取每个任务的算力需求
        }

        // 初始化二分查找的左右边界
        int l = 1; // 最小算力
        int r = (int) 1e9; // 最大算力

        // 进行二分查找
        while (l < r) {
            int mid = (l + r) >> 1; // 计算中间值

            // 检查当前算力 mid 是否满足条件
            if (check(a, mid, T)) {
                r = mid; // 如果满足条件，尝试更小的算力
            } else {
                l = mid + 1; // 否则，增加算力
            }
        }

        // 输出找到的最低算力
        System.out.println(l);
    }

    // 检查给定算力 y 是否能够在 T 时刻内完成所有任务
    private static boolean check(int[] a, int y, int T) {
        int cur = 0; // 当前时刻内的算力总和
        int res = 1; // 当前使用的时刻数

        // 遍历每个任务的算力需求
        for (int x : a) {
            // 如果当前任务的算力加上当前总和超出 y
            if (cur + x > y) {
                res += 1; // 需要增加一个时刻
                cur = 0; // 重置当前算力总和
            }

            cur += x; // 将当前任务的算力加到当前总和

            // 如果在分配任务时当前算力超过了 y，返回 false
            if (cur > y) {
                return false;
            }
        }

        // 返回使用的时刻数是否小于等于 T
        return res <= T;
    }
}

Python

# 读取输入：N 为任务数量，T 为可用的时刻数
N, T = map(int, input().split())
# 读取每个任务的算力需求，并存储在列表 a 中
a = list(map(int, input().split()))

# 初始化二分查找的左右边界
l, r = 1, int(1e9)

# 定义检查函数 check(y)，用于判断当前算力 y 是否能够在 T 时刻内完成所有任务
def check(y):
    cur, res = 0, 1  # cur 表示当前时刻的算力总和，res 表示当前使用的时刻数
    for x in a:  # 遍历每个任务的算力需求
        # 如果当前任务的算力加上当前总和超出 y
        if cur + x > y:
            res += 1  # 需要增加一个时刻
            cur = 0  # 重置当前算力总和
        cur += x  # 将当前任务的算力加到当前总和
        # 如果在分配任务时当前算力超过了 y，说明不满足条件
        if cur > y:
            return False
    # 返回使用的时刻数是否小于等于 T
    return res <= T

# 进行二分查找
while l < r:
    mid = (l + r) >> 1  # 计算中间值
    if check(mid):  # 如果当前算力 mid 能满足条件
        r = mid  # 尝试更小的算力
    else:  # 否则，增加算力
        l = mid + 1  # 尝试更大的算力

# 输出找到的最低算力
print(l)

C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int N, T; // N为任务数量，T为时刻数量
    cin >> N >> T;

    vector<int> a(N); // 存储每个任务的算力需求
    for (int i = 0; i < N; ++i) {
        cin >> a[i];
    }

    int l = 1; // 最小算力
    int r = 1e9; // 最大算力

    // 检查给定算力y是否能够在T时刻内完成所有任务
    auto check = [&](int y) {
        int cur = 0; // 当前时刻内的算力总和
        int res = 1; // 当前时刻数

        for (int x : a) {
            // 如果当前任务的算力加上当前总和超出y
            if (cur + x > y) {
                res += 1; // 需要新增一个时刻
                cur = 0; // 重置当前算力
            }

            cur += x; // 增加当前任务的算力

            // 如果在分配任务时当前算力超过了y，返回false
            if (cur > y) {
                return false;
            }
        }

        // 返回使用的时刻数是否小于等于T
        return res <= T;
    };

    // 二分查找
    while (l < r) {
        int mid = (l + r) >> 1; // 计算中间值

        if (check(mid)) { // 如果满足条件，说明算力可以更低
            r = mid; // 缩小右边界
        } else { // 否则，增加算力
            l = mid + 1; // 缩小左边界
        }
    }

    cout << l << endl; // 输出找到的最低算力

    return 0;
}

题目描述

现有训练子任务模型的列表tasks, tasks[i]表示第i个子任务的算力需求，为了保证模型计算的时间，要求所有任务在T时刻内完成计算。

每个时刻，需要按照给出子任务模型的算力需求列表调度到量子计算机完成计算，任意时刻调度的多个子任务的算力需求综合不能超过量子计算机的最大算力负荷。

请返回量子计算机所需要提供的最低算力，可以在T时刻内计算完全部子任务模型

输入描述

输入：包含两行，第一行2个整数N, T，分别表示子任务模型列表长度，计算子任务模型的时刻要求。

第二行包含N个整数：task[1] task[2] task[3] ... task[n]分别表示第i个子任务的算力需求

输出描述

输出：一行包含一个整数，表示量子计算机所需要的最低算力

备注：

• 1 <= T <= N <= 50000
• 1 <= tasks[i] <= 500

示例1

输入

10 5
1 2 3 4 5 6 7 8 9 10

输出

15

说明： 最低算力需求为15时，可以在5时刻范围内完成所有任务 时刻1: 完成1，2,3,4,5的任务；时刻2：完成6,7的任务；时刻3：完成8任务；时刻4：完成9任务；时刻5：完成10任务

示例2

输入

6 3
4 4 2 1 2 3

输出

6

说明：

时刻1:4； 时刻2:4,2； 时刻3:1,2,3