1# 胖哥购物(shopping.cpp/c/pas)
Description
今天,胖哥在淘宝上购物。刚开始,胖哥的手上没有任何的优惠券。已知在购物过程中,胖哥将会按顺序遇到 n 个事件:
1 x:购买一个价值为 x 的商品。当发生这种事时,胖哥最多只能使用一张面值小于 x的优惠券去减免。若手中没有优惠券,则全额购买。
2 x:得到一张 x 元的优惠券。
胖哥想知道,在最优的策略下,完成今天的购物最少要花掉多少钱。
Format
Input
共 n+1 行,第一行包含一个整数 n,表示事件的个数。
接下来 n 行,每行两个正整数 type x。若 type=1,表示是事件 1,若 type=2,表示是事件 2。
Output
输出共一行,包含一个整数,表示完成今天的购物最少要花掉多少钱。
Sample 1
Input
10
2 4
1 6
1 6
2 4
1 1
2 2
2 3
2 3
1 3
1 6
Output
12
Limitation
1s, 256MiB for each test case.
【数据说明】
对于 30%的数据,1≤n≤10。
对于 60%的数据,1≤n≤1000。
对于 100%的数据,1≤n≤100000。
对于 100%的数据,1≤x≤100000。
Source
2018年泉州复赛模拟提高组 day3t1
信息
- 难度
- 9
- 分类
- (无)
- 标签
- 递交数
- 7
- 已通过
- 4
- 通过率
- 57%
- 上传者