思路

将卡片分成两类： $b \ge 1$ 与 $b = 0$ 。
先把所有 $b \ge 1$ 的卡全部抽掉。理由：这类卡不会减少当前可抽次数（ $b=1$ 不变， $b>1$ 增加），越早抽越能“解锁”更多后续机会。抽完这些卡后的剩余可抽次数：
$t = 1 + \sum_{b_i \ge 1}(b_i - 1)$
然后在 $b=0$ 的卡中，按 $a$ 从大到小选取前 $\min(t, m)$ 张（ $m$ 为 $b=0$ 的张数）。

P3469.第2题-抽卡

1000ms

Tried: 46

Accepted: 29

Difficulty: 3

所属公司 : 得物

算法与标签>贪心算法

题目内容

抽卡是一个类似于博弈的游戏。现在有一种抽卡方式，描述如下:初始你只有一次抽卡机会。每次抽卡浪费一次抽卡机会，获得一张卡片。有两个数字，第一个数字代表你哪获得的钱，第二个数字代表你能获得的额外抽卡次数。额外的抽卡次数是可以累计的。现在，你知道了卡所有的卡片上的数字，以及所有卡片的顺序。你只需要安排一种抽卡顺序，使得你能获得钱数最多。 $0≤a_i,b_i≤1000,1≤n≤1000$

输入描述

第一个行一个数 $n$ ,代表卡片的数量。接下来 $n$ 行，每行用两个数 $a_i,b_i$ ,描述一张卡片。 $a_i$ 表示抽这张卡能获得的钱数， $b_i$ 表示抽这张卡能获得抽卡次数。

输出描述

一行一个数，代表你能获得的最多钱数。

样例1

输入

输出

说明

样例解释：按顺序抽第张卡

输入

预期输出（选填）

思路

P3469.第2题-抽卡

题目内容

输入描述

输出描述

样例1

Status

Development

Support

About