比赛场次 615
比赛名称 2024暑假C班集训5
比赛状态 已结束比赛成绩
开始时间 2024-07-05 08:00:00
结束时间 2024-07-05 12:00:00
开放分组 全部用户
注释介绍 由于 COGS 特性,题目顺序完全乱序,请自行决策开题顺序。
组题人主观难度顺序:T2 < T1 < T4 < T3。
题目名称 任务
输入输出 task.in/out
时间限制 1000 ms (1 s)
内存限制 512 MiB
测试点数 10 简单对比
用户 结果 时间 内存 得分
Gravatarliuyiche AAATTTTTTT 7.000 s 4.13 MiB 30
Gravatar┭┮﹏┭┮ WAAWWWWWWW 0.005 s 0.58 MiB 20
Gravatar陆晨洗 AWWWWWWWWW 0.000 s 0.00 MiB 10
Gravatar蜀山鸭梨大 WAWWWWWWWW 0.000 s 0.00 MiB 10
GravatardarkMoon WAWWWWWWWW 0.009 s 1.17 MiB 10
Gravatar123 AWWTTTTTTT 7.000 s 4.02 MiB 10
Gravatar小金 AWWTTTTTTT 7.000 s 4.02 MiB 10
Gravatar彭欣越 AWWTTTTTTT 7.000 s 4.03 MiB 10
Gravatarwzh0425 AWWTTTTTTT 7.000 s 4.03 MiB 10
Gravatarflyfree AWWTTTTTTT 7.000 s 4.04 MiB 10
Gravatardream WWWWWWWWWW 0.000 s 0.00 MiB 0
Gravatar健康铀 WWWWWWWWWW 0.007 s 0.58 MiB 0
Gravatarwdsjl WWWWWWWWEW 1.269 s 4.82 MiB 0
GravatarUntitled WWWTTTTTTT 7.000 s 4.02 MiB 0
GravatarAeeE5x WWWTTTTTTT 7.000 s 4.03 MiB 0

任务

★★   输入文件: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$。

【来源】

经典问题。