题目描述

Dpstr开了个饮料连锁店，连锁店共有n家，出售的饮料种类相同。为了促销，Dpstr决定让每家连锁店开展赠送活动。具体来说，在第i家店，顾客可以用ai个饮料瓶兑换到bi瓶饮料和1个纪念币（注意不足ai个饮料瓶则不能兑换）。一家店可以兑换多次，兑换得到的饮料瓶还可以继续用于兑换。

小C买了s瓶饮料，他想知道用这s瓶饮料最多可以兑换到多少个纪念币。

数据范围

对于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。

解法

贪心：以差值为第一关键字，x为第二关键字，尽可能做靠前的。

代码

#include<iostream>

#include<stdio.h>

#include<string.h>

#include<math.h>

#include<algorithm>

#define ll long long

using namespace std;

const char* fin="store.in";

const char* fout="store.out";

const unsigned ll inf=0x7fffffff;

const unsigned ll maxn=100007;

unsigned ll n,m,i,j,k,ans;

struct node{

    unsigned ll x,y;

}a[maxn];

bool cmp(node a,node b){

    return a.y<b.y || a.y==b.y && a.x<b.x;

}

int main(){

    freopen(fin,"r",stdin);

    freopen(fout,"w",stdout);

    scanf("%llu%llu",&n,&m);

    for (i=1;i<=n;i++){

        scanf("%llu%llu",&a[i].x,&a[i].y);

        a[i].y=a[i].x-a[i].y;

    }

    sort(a+1,a+n+1,cmp);

    for (i=1;i<=n;i++){

        if (m>=a[i].x){

            if (a[i].y<=0){

                printf("-1");

                return 0;

            }

            k=(m-a[i].x)/a[i].y+1;

            ans+=k;

            m-=k*a[i].y;

        }

    }

    printf("%llu",ans);

    return 0;

}

启发

输出unsigned时使用%llu，实在不行，用cout