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=100005;
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=0;
    for (i=1;i<=n;i++)
    {
         scanf("%llu%llu",&a[i].a,&a[i].b);
    }
    sort(a+1,a+n+1,cmp);
    for (i=1;i<=n;i++)
        if (a[i].a-a[i].b<=0 && a[i].a<=m){
            printf("-1\n");
            return 0;
        }
    for (i=1;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!!!!!!!!

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-22 16:33
重庆工商大学_2024
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-15 10:17
厦门大学_2023
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议