DAY2模拟考試第二題 連鎖店

2、連鎖店

（store.pas/c/c++）

【題目描述】

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

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

【輸入格式】

輸入檔案名為store.in。

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

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

【輸出格式】

輸出檔案名為store.out。

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

【樣例輸入1】

3 11

4 1

5 2

8 4

【樣例輸出1】

3

【輸入輸出樣例1說明】

最多兌換到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個紀念币。

【輸入輸出樣例2】

見選手檔案夾下的store/store2.in和store/store2.ans

【資料範圍】

對于30%的資料，0<=n<=10, 0<=s<=20；

對于50%的資料，0<=n<=1000 ,0<=s<=100 000；

對于100%的資料，0<=n<=100 000 ,0<=s<=1019 ,0<=ai<=1019 ,0<=bi<=1019。

#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define ll  unsigned long long
using namespace std;
const int maxn=;
struct NODE{
    ll a,b;
}a[maxn];
ll m,t,ans;
ll n,i,j,k,l;
inline bool cmp(NODE x,NODE y){
    return x.a-x.b<y.a-y.b||x.a-x.b==y.a-y.b&&x.a<y.a; 
}
int main(){
   freopen("store.in","r",stdin);
   freopen("store.out","w",stdout);
    scanf("%llu%llu",&n,&m);
    bool flag=;
    for (i=;i<=n;i++)
    {
         scanf("%llu%llu",&a[i].a,&a[i].b);
    }
    sort(a+,a+n+,cmp);
    for (i=;i<=n;i++)
        if (a[i].a-a[i].b<= && a[i].a<=m){
            printf("-1\n");
            return ;
        }
    for (i=;i<=n;i++){
        if (m>=a[i].a){
            t=(m-a[i].a)/(a[i].a-a[i].b);
            t++;
            m-=(a[i].a-a[i].b)*t;
            ans+=t;
        }
    }
    printf("%llu\n",ans);
}
           

這道題需要unsigned long long …….

就是貪心，按內插補點排序

然後注意判0！！！！！！！！