Codeforces Round #727 (Div. 2) D. PriceFixed

 翻译：

莉娜是莫斯科最节俭的女孩。所以，当她爸爸让她为去乡村旅行买一些食物时，她去了最好的商店——“PriceFixed”。这里是那家商店的一些规则:

这家商店每种产品都有无限多的品种。
所有产品都有相同的价格:每件2卢布。
对于每一个产品𝑖有一个折扣经验的买家:如果你购买𝑏𝑖的产品(任何类型，不一定是𝑖类型)，那么对于所有未来购买𝑖-th的产品有50%的折扣(所以你可以购买𝑖-th的产品1卢布!)
Lena需要购买𝑛产品:她必须至少购买𝑖-th产品的𝑎𝑖项。帮助Lena计算她需要花费的最小金额，如果她选择了最佳的购买顺序。请注意，如果她愿意，她可以购买比需要更多的产品。

输入
第一行包含单个整数𝑛(1≤𝑛≤100000)——产品的数量。

接下来的每一行𝑛都包含一个产品描述。每个描述由两个整数𝑎𝑖和𝑏𝑖(1≤𝑎𝑖≤1014,1≤𝑏𝑖≤1014)组成——𝑖-th产品的所需数量和您需要购买多少产品才能获得𝑖-th产品的折扣。

所有𝑎𝑖的和不超过1014。

输出
输出莉娜完成所有购买所需的最小金额。

例子
inputCopy
3.
3 4
1 3
１ ５
outputCopy
8
inputCopy
5
2 7
2 8
1 2
2 4
1 8
outputCopy
12
请注意
在第一个例子中，Lena可以通过以下方式购买产品:

2卢布一件3号产品，
1号产品2卢布，
1号产品2卢布，
1卢布一件商品2件(她可以使用折扣，因为她已经购买了3件商品)，
1卢布购买1件商品(她可以使用折扣，因为她已经购买了4件商品)。
她总共花了8卢布。可以证明，少花钱是不可能的。

在第二个例子中，Lena可以通过以下方式购买产品:

1号产品2卢布，
两件产品2，每件2卢布，
一件5的产品2卢布，
一件产品三件一卢布，
两件4件，每件1卢布，
1卢布一件产品。
她总共花了12卢布。

题意：买东西，如何最优购买方案，花最少的钱，如果买的东西数量达到了打折数量，则有50%的优惠，问你最少用多少钱买完

思路：典型的贪心，最少的钱买完，肯定先买最难到达的，然后如果到达了可以打折的就先买打折的，因为已经打折了，是最便宜的，后面难到达打折的，也有可能达到打折，这样来回选着买。无非就是贪心+双指针的典型问题，结构题排序，然后双指针。

代码实现：

#include 
#include 
#include 
#include 
#include 
#include 
#include
#include
#include
#include

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！