P15843 [Bulgarian NOI 2024] 显卡 / GPUs
题目背景
在洛谷上提交此题，请选择 >=C++17 的语言标准，不需要引入 `#include "gpus.h"`，而是将
```cpp
#include
#include
#include
inline std::ostream& operator
题目描述
作为一家现代创业公司的创始人，你们启动了一个生成式 AI 项目。图像、文本等的生成过程被拆分为 $N$ 个任务，每个任务需要恰好一台 GPU（显卡）运行一秒钟。你预先知道每个任务何时可用——任务 $i$ 在第 $T_i$ 秒变为可执行状态。你可以使用一台拥有 $M$ 块 GPU 的外部超级计算机，但每块 GPU 的使用成本不同：第 $j$ 块 GPU 每秒花费 $C_j$。你需要为每个任务 $i$ 分配一块特定的 GPU $j$ 和一个具体的时间点，使得该时间点不早于 $T_i$，且在同一时刻、同一块 GPU 上没有其他任务被调度。换言之，每块 GPU 在任意给定秒内最多只能处理一个任务。
设最终完成时间为 $F$（即所有任务中最晚的调度时间加一），总支付金额为 $S$。若任务 $i$ 被分配给 GPU $G_i$，则 $S = C_{G_1} + C_{G_2} + \dots + C_{G_N}$。你的目标是找到 $F \times S$ 的最小可能值。你需要独立解决 $Q$ 个该问题的实例。
### 交互说明
本题为交互式题目。你无需从标准输入读取数据或向标准输出写入数据，只需实现一个名为 `solveGpus` 的函数，其定义如下：
```cpp
__int128 solveGpus(
std::vector& gpuCosts,
std::vector& reqTimes
);
```
该函数接收两个 vector 作为参数，这两个 vector 均按**非递减顺序**排序。你可以修改传入的 vector。函数返回类型为 `__int128`，表示一个 128 位整数——这是必要的，因为答案可能超出 `long long` 的范围。该函数会被多次调用，每次调用对应一道独立的题目实例。
你的代码中不应包含 `main` 函数，但可以包含任意其他辅助函数、类、变量等。你的代码必须包含头文件 `gpus.h`，其中为了方便你使用，已定义了用于输出 `__int128` 类型值的运算符。请通过以下预处理指令包含该头文件：
```cpp
#include "gpus.h"
```
你的代码将与评测器一起编译，评测器负责读取输入并写入输出。在评测系统中，唯一计入时间限制的是你的代码实际执行所花费的时间，即输入/输出操作的时间不计入总耗时。
为便于本地测试，我们提供了本地评测器 `Lgrader.cpp` 以及头文件 `gpus.h` 的副本。你需要将自己的代码与本地评测器一同编译，以便进行测试。你可以将它们放在同一目录下，并使用以下命令：
```bash
g++ -O2 -std=c++17 -Wl,--stack,1073741824 -Wall gpus.cpp Lgrader.cpp -o gpus.exe
```
输入格式
本地评测器的输入格式如下：
首先为 $Q$，随后对于每个测试用例：$N, M$，接着是所有 $C_j$ 和所有 $T_i$。
输出格式
无
说明/提示
### 子任务
| 子任务 | 分数 | $N \le$ | $Q \le$ |
|:------:|:----:|:-------:|:-------:|
| $1$ | $10$ | $10$ | $1$ |
| $2$ | $8$ | $800$ | $2$ |
| $3$ | $13$ | $2200$ | $2$ |
| $4$ | $14$ | $10^4$ | $2$ |
| $5$ | $11$ | $10^5$ | $2$ |
| $6$ | $15$ | $10^6$ | $5$ |
| $7$ | $29$ | $10^7$ | $5$ |
只有当成功通过某子任务所对应的所有测试点时，才能获得该子任务的分数。
### 限制条件
- $1 \le N \le 10^7$
- $1 \le M \le N$
- $0 \le T_i \le N$
- $1 \le C_i \le 2N$
- $1 \le Q \le 5$
翻译由 Qwen3.5-397B-A17B 完成