任务分组最小化费用算法：C++ 实现

问题描述

有 N 个任务排成一个序列在一台机器上等待执行，它们的顺序不得改变。机器会把这 N 个任务分成若干批，每一批包含连续的若干个任务。从时刻 0 开始，任务被分批加工，执行第 i 个任务所需的时间是 Ti。

另外，在每批任务开始前，机器需要 S 的启动时间，故执行一批任务所需的时间是启动时间 S 加上每个任务所需时间之和。

一个任务执行后，将在机器中稍作等待，直至该批任务全部执行完毕。也就是说，同一批任务将在同一时刻完成。每个任务的费用是它的完成时刻乘以一个费用系数 Ci。

请为机器规划一个分组方案，使得总费用最小。

输入

第一行是 N。第二行是 S。

下面 N 行每行有一对正整数，分别为 Ti和 Ci，表示第 i 个任务单独完成所需的时间是 Ti及其费用系数 Ci。

输出

一个数，最小的总费用。

输入样例 1

输出样例 1

提示

分组方案为{1,2},{3},{4,5}，则完成时间为{5,5,10,14,14}，费用C={15,10,30,42,56}，总费用为 153。

数据范围与提示

对于全部数据，1≤N≤5000,0≤S≤50,1≤Ti ,C i≤100

C++ 代码内容：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Task {
    int T;
    int C;
};

bool compare(Task a, Task b) {
    return a.T * b.C < b.T * a.C;
}

int main() {
    int N, S;
    cin >> N >> S;
    vector<Task> tasks(N);
    for (int i = 0; i < N; i++) {
        cin >> tasks[i].T >> tasks[i].C;
    }
    sort(tasks.begin(), tasks.end(), compare);

    long long totalCost = 0;
    long long currentTime = 0;
    for (int i = 0; i < N; i++) {
        currentTime += tasks[i].T;
        totalCost += currentTime * tasks[i].C;
    }
    totalCost += S * currentTime;
    cout << totalCost << endl;

    return 0;
}

代码解释：

结构体 Task： 定义结构体 Task 来存储每个任务的信息，包含执行时间 T 和费用系数 C。
比较函数 compare： 定义比较函数 compare，用于根据 T * C 的值对任务进行排序。该排序策略基于贪心算法的思想，将 T * C 值小的任务优先放在一起，因为这些任务的完成时间较早，可以减少总费用。
主函数 main：
- 输入任务数量 N，启动时间 S 以及每个任务的 T 和 C。
- 对任务按照 compare 函数进行排序。
- 初始化总费用 totalCost 和当前时间 currentTime 为 0。
- 遍历所有任务，计算每个任务的完成时间和费用，并累加到总费用中。
- 计算启动时间带来的额外费用并累加到总费用中。
- 输出最终的最小总费用。

代码优化：

可以使用更有效的排序算法，例如快速排序或堆排序，以提高代码的效率。
可以使用累加计算技巧，避免重复计算，进一步优化代码效率。

总结：

本文介绍了如何使用 C++ 算法解决任务分组最小化费用问题。该算法使用贪心算法的思想，对任务进行排序并分组，最终得到最小化的总费用。代码示例清晰易懂，并附带优化建议，可以帮助读者更好地理解和应用该算法。