题目名称 | 3775. 任务 |
---|---|
输入输出 | task.in/out |
难度等级 | ★★ |
时间限制 | 1000 ms (1 s) |
内存限制 | 512 MiB |
测试数据 | 10 |
题目来源 | yrtiop 于2022-10-20加入 |
开放分组 | 全部用户 |
提交状态 | |
分类标签 | |
分享题解 |
通过:3, 提交:26, 通过率:11.54% | ||||
鸣人 | 100 | 0.000 s | 0.00 MiB | C++ |
┭┮﹏┭┮ | 100 | 0.360 s | 51.91 MiB | C++ |
flyfree | 100 | 2.452 s | 465.87 MiB | C++ |
鸣人 | 90 | 0.000 s | 0.00 MiB | C++ |
鸣人 | 80 | 0.000 s | 0.00 MiB | C++ |
鸣人 | 70 | 0.000 s | 0.00 MiB | C++ |
鸣人 | 70 | 0.000 s | 0.00 MiB | C++ |
鸣人 | 70 | 0.000 s | 0.00 MiB | C++ |
鸣人 | 60 | 0.000 s | 0.00 MiB | C++ |
鸣人 | 60 | 0.000 s | 0.00 MiB | C++ |
本题关联比赛 | |||
2024暑假C班集训5 |
关于 任务 的近10条评论(全部评论) |
---|
这里本来应该有一些有趣的题目背景,但我是懒狗,所以大家自己脑补一下。
现在有两台机器 $A$ 和 $B$。有 $n$ 个任务,编号 $1\sim n$。你必须把每个任务安排到一台机器上处理,同时需要满足以下一些条件。
1. 你必须把每个任务安排到任意一台机器上处理。
2. 在任何时刻,一台机器只能最多处理一个任务。
3. 任务 $i(0<i\le n)$ 可以被处理当且仅当每个任务 $j(j<i)$ 已经被完成或者正在进行。
4. 一个任务如果在一台机器上进行,它是不能被打断的。
请你算算最少完成任务的时间。
第一行一个整数 $n$ 表示任务的个数。
接下来 $n$ 行,每行两个整数 $t_A, t_B$,表示完成每个任务在两台机器上花的时间。
输出最早完成任务的时间。
2 1 2 90 95
90
3 1 3 1 3 1 3
3
第一组数据:让 $B$ 机器完成任务 $1$ 同时让 $A$ 机器完成任务 $2$。
第二组数据:让 $A$ 机器完成所有的任务。
对于 $30\%$ 的数据,$1\le n\le 20, 0 < t_A, t_B \le 30$。
对于 $70\%$ 的数据,$1\le n\le 200, 0 < t_A, t_B \le 300$。
对于 $100\%$ 的数据,$1\le n\le 2000, 0 < t_A, t_B \le 3000$。
经典问题。