【NOIP 2016アップA組合宿第7場11.4】チェーン店

Description
Dpstrは飲料チェーン店を開き、チェーン店はn社あり、販売されている飲料の種類は同じだ.プロモーションのため、Dpstrはチェーン店ごとに贈呈活動を行うことにした.具体的には、i番目の店では、ai個のペットボトルをbi瓶飲料と1個の記念貨幣に両替することができます(ai個のペットボトルに足りないと両替できません).ある店では何度も両替できますが、両替したペットボトルは引き続き両替に使えます.Cさんはs本の飲み物を買いました.彼はこのs本の飲み物で最大何個の記念貨幣に両替できるか知りたいです.
Solution
この問題は明らかに欲張りだ.貪欲な考え方は、差値を第一キーワード、aを第二キーワードとし、小さい頃から大きい順に並べて、シミュレーションします.欲張りは明らかで、このような浪費の瓶はもっと小さい.まず、ans=ans+1+(s-a[i].a)/(a[i].a-a[i].b)、s-=k*(a[i].a-a[i].b)、(a[i].a-a[i].b)が小さいほど、a[i].aが小さいほど、最適です.範囲は10^19なのでunsigned long longをつけ、入力はllu
Code

#include
#include
#include
#include
#include
#define fo(i,a,b) for(i=a;i<=b;i++)
using namespace std;
typedef unsigned long long ll;
const int maxn=100007;
ll i,j,l,n,m;
ll t,k,ans;
ll s;
struct node{
    ll a,b;
}a[maxn];
bool cmp(node x,node y){
    return x.a-x.ba-y.b||x.a-x.b==y.a-y.b&&x.aa;
}
int main(){
//  freopen("store.in","r",stdin);
//  freopen("store.out","w",stdout);
    freopen("fan.in","r",stdin);
    scanf("%llu%llu",&n,&s);
    fo(i,1,n){
        scanf("%llu%llu",&a[i].a,&a[i].b);
    }
    sort(a+1,a+1+n,cmp);
    fo(i,1,n){
        if(a[i].a<=a[i].b&&s>=a[i].a){
            printf("-1
");
            return 0;
        }
    }
    fo(i,1,n){
        while(s>=a[i].a){
            k=(s-a[i].a)/(a[i].a-a[i].b);
            k++;
            ans+=k;
            s-=k*(a[i].a-a[i].b);
        }
    }
    printf("%llu
",ans);
}