SSL2560 2016年提高組模拟試題 連鎖店（貪心）

2016年提高組模拟試題（20161109）連鎖店

Description

Dpstr開了個飲料連鎖店，連鎖店共有n家，出售的飲料種類相同。為了促銷，Dpstr決定讓每家連鎖店開展贈送活動。具體來說，在第i家店，顧客可以用ai個飲料瓶兌換到bi瓶飲料和1個紀念币（注意不足ai個飲料瓶則不能兌換）。一家店可以兌換多次，兌換得到的飲料瓶還可以繼續用于兌換。

小C買了s瓶飲料，他想知道用這s瓶飲料最多可以兌換到多少個紀念币。

Input

輸入檔案名為store.in。

輸入第一行為兩個整數n，s，分别表示連鎖店的數量和小C的飲料瓶數。

接下來n行，每行兩個整數ai，bi，描述第i家飲料店的贈送活動。

Output

輸出一行一個整數，表示小C最多能兌換到的紀念币數量。若小C能兌換到無限多個紀念币，則輸出-1。

Sample Input

3 11

4 1

5 2

8 4

Sample Output

3

Hint

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。

Hint

最多兌換到3個紀念币。兌換過程如下：

（1）在第1家店用4瓶換1瓶，此時剩11-4+1=8瓶，有1個紀念币；

（2）在第1家店用4瓶換1瓶，此時剩8-4+1=5瓶，有2個紀念币；

（3）在第2家店用5瓶換2瓶，此時剩5-5+2=2瓶，有3個紀念币；

剩餘的飲料瓶無法在任何店兌換，是以最多兌換到3個紀念币。

分析：以內插補點為第一關鍵字，ai為第二關鍵字排序，能選就選。

代碼

#include <cstdio>
#include <algorithm>
#define ll unsigned long long
#define maxn 1000005
using namespace std;

struct arr
{
    ll a,b,c;
}x[maxn];
ll n,s;

bool so(arr p,arr q)
{
    if (p.c==q.c) return p.a<q.a;
    return p.c<q.c;
}

int main()
{
    scanf("%d%llu",&n,&s);
    bool fl=false;
    for (int i=;i<=n;i++)
    {
        scanf("%llu%llu",&x[i].a,&x[i].b);
        if (x[i].a<=x[i].b&&s>=x[i].a) fl=true;
        x[i].c=x[i].a-x[i].b;
    }
    if (fl) printf("-1");
    else
    {
        sort(x+,x+n+,so);
        ll ans=;
        for (int i=;i<=n;i++)
            if (s>=x[i].a)
            {
                ans+=(s-x[i].a)/x[i].c+;
                s-=((s-x[i].a)/x[i].c+)*x[i].c;
            }
        printf("%llu",ans);
    }
}