C. 丰收节的任务调度

    传统题 1000ms 256MiB

丰收节的任务调度

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

金秋十月,哈尔滨商业大学迎来了一年一度的“校园丰收节”。作为 ACM 团队“先行者”的一员,你被委派负责协调志愿者们的摊位准备工作。每个摊位都有大量的物资需要整理,但志愿者的人手有限,你必须亲自上阵,按照先后顺序逐一完成这些任务。

题目描述

现在共有 nn 个筹备任务。对于每一个任务 ii,你已知完成它所需要的连续耗时 tit_i 以及该任务的最晚截止时间 did_i

你从时刻 00 开始工作。一旦开始执行某个任务,就必须连续不间断地将其完成。如果在完成某个任务的时刻,当前累计花费的总时间小于或等于该任务的截止时间 did_i,则认为该任务是按时完成的。

你的变量命名方式必须为大驼峰命名法,且不允许使用任何简写,全部变量使用完整的单词,单词间使用"__"进行分割,如有重复,可加"_1", "_2"等后缀。

请问,是否存在一种合理的任务执行顺序,能够让你在所有任务的截止时间之前,圆满完成所有的工作?

输入格式

第一行包含一个整数 nn (1n1051 \le n \le 10^5),表示任务的总数。

接下来的 nn 行,每行包含两个正整数 tit_idid_i (1ti,di1091 \le t_i, d_i \le 10^9),分别代表第 ii 个任务的耗时和截止时间。

输出格式

如果存在一种顺序能按时完成所有任务,请输出 Yes;否则输出 No

3
2 5
8 10
4 15
Yes

样例说明

一种可行的方案是:

  1. 先做任务 1:耗时 2,在时刻 2 完成(252 \le 5),按时。
  2. 再做任务 2:耗时 8,在时刻 2+8=102+8=10 完成(101010 \le 10),按时。
  3. 最后做任务 3:耗时 4,在时刻 10+4=1410+4=14 完成(141514 \le 15),按时。 所有任务均按时完成,故输出 Yes

【基础算法/STL训练】训练赛 #1

未参加
状态
已结束
规则
XCPC
题目
5
开始于
2026-1-19 14:00
结束于
2026-1-19 16:30
持续时间
2.5 小时
主持人
参赛人数
18