1028-贪心 · 例7-活动安排_2021秋季算法入门班第一章习题：模拟、枚举、贪心

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 对于给定的 $n$ 个活动，我们使用一个二元组 $\{c_i,d_i\}$ 来描述第 $i$ 个活动的具体情况，这代表这个活动需要花费 $c_i$ 个单位的时间来完成，并且截止时间为 $d_i$ 。记你完成这个活动的时间为 $t$ ，当这个时间大于 $d_i$ 时，会被扣除 $t - d_i$ 点分数；而当 $t \leqq d_i$ 时分数不会发生变化。
$\hspace{15pt}$ 现在，你需要合理的安排自己完成这 $n$ 个活动的顺序，使得自己的扣分值最大的那个活动扣分值最小。

$\hspace{15pt}$ 需要注意的是，在同一时间你只能进行一个活动，且不能中途停止；在上一个活动结束的同时你可以无缝进行下一个活动，切换时间忽略不计。

输入描述:

第一行输入一个整数  代表活动的数量。
此后  行，第  行输入两个整数  代表第  个活动需要的时间、截止的时间。

输出描述:

在一行上输出一个整数，代表最小的扣分。

示例1

输入

复制

2
5 3
4 6

输出

复制

说明

在这个样例中，其中一种安排方式是先进行活动一、再进行活动二：
在活动一完成时， ，扣除  点分数；
在活动二完成时， ，扣除  点分数；

另一种安排方式是先进行活动二、再进行活动一：
在活动二完成时， ，分数不变化；
在活动一完成时， ，扣除  点分数；

综上所述，第一种安排更优，扣分值最大的那个活动扣分值最小为 。

备注:

本题已于下方时间节点更新，请注意题解时效性：
1. 2025-06-13 更新题面与 std。
2. 2025-03-04 更新题面与 std。
3. 2024-11-07 更新题面。