题目描述

有n只怪兽，初始你有k点血量，打第i个怪兽至少需要$a_i$的血量，打完第i个怪兽之后会掉$b_i$的血量，你可以按照任何顺序依次打完所有怪兽，并给出一种方案。

$\large n\leq10^6\qquad a_i,b_i\leq10^9$

题目解析

设$n\ =\ 2$

第一组：$a_1\qquad b_1$
第二组：$a_2\qquad b_2$

则k需要满足条件
① $\large k\geq\max(a_1,a_2)$
②若先打第一组
$\large k-b_1\le a_2$
$\large \implies k\ge a_2+b_1$
同理，若先打第二组
$\large k\ge a_1+b_2$

比较$a_2+b_1$与$a_1+b_2$的大小
由于$k$在操作之后会变小，所以让大的先打，这样才能尽量多地打。

$\implies a_2+b_1?>a_1+b_2$
$\implies a_2-b_2?>a_1-b_1$
$\implies$扩展到n个数，我们只需要将$a_n-b_n$从大到小排列，依次执行就好了。

程序代码

略