题目名称 3775. 任务
输入输出 task.in/out
难度等级 ★★
时间限制 1000 ms (1 s)
内存限制 512 MiB
测试数据 10
题目来源 Gravataryrtiop 于2022-10-20加入
开放分组 全部用户
提交状态
分类标签
动态规划
分享题解
通过:3, 提交:26, 通过率:11.54%
Gravatar鸣人 100 0.000 s 0.00 MiB C++
Gravatar┭┮﹏┭┮ 100 0.360 s 51.91 MiB C++
Gravatarflyfree 100 2.452 s 465.87 MiB C++
Gravatar鸣人 90 0.000 s 0.00 MiB C++
Gravatar鸣人 80 0.000 s 0.00 MiB C++
Gravatar鸣人 70 0.000 s 0.00 MiB C++
Gravatar鸣人 70 0.000 s 0.00 MiB C++
Gravatar鸣人 70 0.000 s 0.00 MiB C++
Gravatar鸣人 60 0.000 s 0.00 MiB C++
Gravatar鸣人 60 0.000 s 0.00 MiB C++
本题关联比赛
2024暑假C班集训5
关于 任务 的近10条评论(全部评论)

3775. 任务

★★   输入文件:task.in   输出文件:task.out   简单对比
时间限制:1 s   内存限制:512 MiB

【题目描述】

这里本来应该有一些有趣的题目背景,但我是懒狗,所以大家自己脑补一下。

【题目描述】

现在有两台机器 $A$ 和 $B$。有 $n$ 个任务,编号 $1\sim n$。你必须把每个任务安排到一台机器上处理,同时需要满足以下一些条件。

1. 你必须把每个任务安排到任意一台机器上处理。

2. 在任何时刻,一台机器只能最多处理一个任务。

3. 任务 $i(0<i\le n)$ 可以被处理当且仅当每个任务 $j(j<i)$ 已经被完成或者正在进行。

4. 一个任务如果在一台机器上进行,它是不能被打断的。

请你算算最少完成任务的时间。

【输入格式】

第一行一个整数 $n$ 表示任务的个数。

接下来 $n$ 行,每行两个整数 $t_A, t_B$,表示完成每个任务在两台机器上花的时间。

【输出格式】

输出最早完成任务的时间。

【样例输入 1】

2
1 2
90 95

【样例输出 1】

90

【样例输入 2】

3
1 3
1 3
1 3

【样例输出 2】

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$。

【来源】

经典问题。