web analytics

JZOJ4859 连锁店 解析报告

Description
Dpstr开了个饮料连锁店,连锁店共有n家,出售的饮料种类相同。为了促销,Dpstr决定让每家连锁店开展赠送活动。具体来说,在第i家店,顾客可以用ai个饮料瓶兑换到bi瓶饮料和1个纪念币(注意不足ai个饮料瓶则不能兑换)。一家店可以兑换多次,兑换得到的饮料瓶还可以继续用于兑换。
小C买了s瓶饮料,他想知道用这s瓶饮料最多可以兑换到多少个纪念币。

Input

输入文件名为store.in。
输入第一行为两个整数n,s,分别表示连锁店的数量和小C的饮料瓶数。
接下来n行,每行两个整数ai,bi,描述第i家饮料店的赠送活动。

Output

输出文件名为store.out。
输出一行一个整数,表示小C最多能兑换到的纪念币数量。若小C能兑换到无限多个纪念币,则输出-1。

Sample Input

样例输入1:
3 11
4 1
5 2
8 4
Sample Output

样例输出1:
3

Data Constraint
对于30%的数据,0≤n≤10,0≤s≤20;
对于50%的数据,0≤n≤1,000,0≤s≤100,000;
对于100%的数据,0≤n≤100,000,0≤s≤10^19,0≤ai≤10^19,0≤bi≤10^19。

本题分析:

这道题看上去,很迷。拿上会有DP的感觉。但是想一想。不用那么麻烦。其实我们就用贪心就可以解决这个问题。因为假设我们取了个优的结果(合适的取方案)。其实如果我们找其他的结果(其他取的方案),一定不会比优的结果更优(就是这样)。
而这里我们怎么样贪心呢?
这里我们可能会想到 用比值(换出去的与换回来的)。不过如果我们用比值来解这道题。这里会存在如果换出去与换回来的数值都特别大。但是这道题里:换一次才得到一个金币所以这里我们必须优先考虑多换而不是换多。。所以这里得用两数的差为第一关键字,之后以换出去的数值为第二关键字。排序。
从第一种方式开始贪心拿,直接从全部拿完第一种方式。

这里就存在一个很迷的问题就是。难道我们要一个一个的去减,加,直到达到要求,再取下一种方法吗?显然不可能。所以用数学来优化一下这个循环。

Because:

假设x为可以-a+b的次数

so :

so:

so:

Because: x为正整数

so: 为正整数。

所以这里我们分类讨论

>

so:

2>

so:

总上所述:

so:

so:

so:
所以我们根据以上的解释。我们就可以很简单的来写这一段的贪心。
放出代码:

Post a Comment

You must be logged in to post a comment.