TYVJ P1032 零用钱 Label:贪心

TYVJ P1032 零用钱 Label:贪心

背景

USACO OCT09 7TH

描述

作為创造產奶纪录的回报,Farmer John决定开始每个星期给Bessie一点零花钱。

FJ有一些硬币,一共有N (1 <= N <= 20)种不同的面额。每一个面额都能整除所有比它大的面额。

他想用给定的硬币的集合,每个星期至少给Bessie某个零花钱的数目C (1 <= C <= 
100000000)。请帮他计算他最多能支付多少个星期的零花钱。

输入格式

* 第一行: 两个由空格隔开的整数: N 和 C

* 第2到第N+1行: 每一行有两个整数表示一个面额的硬币:硬币面额V (1 <= V <= 
100,000,000)和Farmer John拥有的该面额的硬币数B (1 <= B <=
        1,000,000).

输出格式

* 第一行: 一个单独的整数,表示Farmer John最多能给Bessie支付多少个星期至少為C的零用钱。

测试样例1

输入

3 6 

10 1 

1 100 

5 120

输出

111

备注

FJ想要每个星期给Bessie六美分。他有100个1美分硬币,120个5美分硬币,和一个10美分硬币。

FJ可以在一个星期超额付给Bessie一个10美分硬币。然后接下来的10个星期每星期付给
Bessie两个5美分硬币。最后100个星期每星期付给Bessie一个1美分硬币跟一个5美分硬
币。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
int N,C,ans,flag=1,k;
struct cc{
    int mon,num;
}a[25];

bool cmp(cc a,cc b){
    return a.mon<b.mon;
}

void init_(){
    scanf("%d%d",&N,&C);
    for(int i=1;i<=N;++i){
        scanf("%d%d",&a[i].mon,&a[i].num);
    }
    sort(a+1,a+N+1,cmp);
}

void solve(){
    for(int i=N;i>=1;--i){
        while(a[i].num>0&&k-a[i].mon>0){
            --a[i].num;
            k-=a[i].mon;
        }
    }
    for(int i=1;i<=N;++i){
        while(a[i].num>0&&k>0){
            --a[i].num;
            k-=a[i].mon;
        }
    }
}

int main(){
//    freopen("01.txt","r",stdin);
    init_();
    
    while(flag){
        flag=0;
        k=C;
        solve();
        if(k<=0){
            ++ans;
            flag=1;
        }
    }
    
    printf("%d\n",ans);
    return 0;
}

贪心,记得排序

吐槽一下,usaco很喜欢奶牛?这几天tyvj做下来全是奶牛

转载于:https://www.cnblogs.com/radiumlrb/p/5797243.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/108901.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 这可能是目前最全的Redis高可用技术解决方案总结

    这可能是目前最全的Redis高可用技术解决方案总结

  • spring applicationContext.xml 配置文件 详解「建议收藏」

    spring applicationContext.xml 配置文件 详解「建议收藏」applicationContext.xml文件

    2022年7月26日
  • acm总结帖_By AekdyCoin

    acm总结帖_By AekdyCoinacm总结帖_ByAekdyCoin各路大牛都在中国大陆的5个赛区结束以后纷纷发出了退役帖,总结帖,或功德圆满,或死不瞑目,而这或许又会造就明年的各种“炸尸”风波。为了考虑在发退役贴以后明年我也成为“僵尸”的可能性,于是改名曰“总结贴”,不提比赛细节,不提比赛流水账,权当是大学本科生涯中acm生活的点滴记录……(1)入门篇甲PS:以下内容…

  • 硬盘的读写原理详解

    硬盘的读写原理详解硬盘的种类主要是SCSI、IDE、以及现在流行的SATA等;任何一种硬盘的生产都要一定的标准;随着相应的标准的升级,硬盘生产技术也在升级;比如SCSI标准已经经历了SCSI-1、SCSI-2、SCSI-3;其中目前咱们经常在服务器网站看到的Ultral-160就是基于SCSI-3标准的;IDE遵循的是ATA标准,而目前流行的SATA,是ATA标准的升级版本;IDE是并口设备,而SA

  • matlab行列式的转置_matlab行列式左右翻转

    matlab行列式的转置_matlab行列式左右翻转行列式转置,值不变>>a3=[6231;1215;5231;4121]a3=6231121552314121>&gt

  • 冯诺依曼体系结构「建议收藏」

    冯诺依曼体系结构「建议收藏」目录冯诺依曼体系结构简介数据流向存储分级举例说明数据的流动过程冯诺依曼体系结构简介我们常见的计算机,如笔记本。我们不常见的计算机,如服务器,大部分都遵守冯诺依曼体系。计算机本质上是有输入,并且经过计算机的计算,将结果显示到某种显示输出上,就可以称为计算机。输入单元:键盘,网卡,磁盘,话筒…输出单元:显示器,网卡,磁盘,音响…存储器没有特殊说明一般指的是物理内存。中央处理器(CPU):含有运算器和控制器等运算器在进行运算的时候无外乎两种情况,一种是算术运算,一种逻辑运算。控制器主要能够用来

    2022年10月23日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号