hdu-2546-饭卡

简介: hdu-2546-饭卡


饭卡

Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 16708    Accepted Submission(s): 5813


Problem Description

电子科大本部食堂的饭卡有一种很诡异的设计,即在购买之前判断余额。如果购买一个商品之前,卡上的剩余金额大于或等于5元,就一定可以购买成功(即使购买后卡上余额为负),否则无法购买(即使金额足够)。所以大家都希望尽量使卡上的余额最少。

某天,食堂中有n种菜出售,每种菜可购买一次。已知每种菜的价格以及卡上的余额,问最少可使卡上的余额为多少。

 


Input

多组数据。对于每组数据:

第一行为正整数n,表示菜的数量。n<=1000。

第二行包括n个正整数,表示每种菜的价格。价格不超过50。

第三行包括一个正整数m,表示卡上的余额。m<=1000。


n=0表示数据结束。

 


Output

对于每组输入,输出一行,包含一个整数,表示卡上可能的最小余额。

 


Sample Input

      1 50 5 10 1 2 3 2 1 1 2 3 2 1 50 0      

 


Sample Output

      -45 32      

 


Source

UESTC 6th Programming Contest Online

 


Recommend

lcy   |   We have carefully selected several similar problems for you:   2955  1203  2159  2191  1114



题目分析:  其实还是背包,但是读完题好像感觉没有 体积 只有 价值是吧!其实你把饭的价值 当成  体积 和价值就行了,其实他的价值就是体积,体积就是价值

                    但是还有一点 因为是要花最多的钱,而且还可以 把卡上的钱花成负数 ,那么你应该懂得,他的下限是 (要想购物卡上必须有5块以上)所以说你要把最贵的物品放                      到   剩余钱,最接近 5快且比五块大的时候买,那么你看是不是很划算。比如说最贵的是1000  ,你卡上剩余 5快 那么你就可以把他买下透支995 哈哈!此时卡上生                      的钱肯定是最少的吧!怎么实现呢,很简单就比背包模板多了一个排序,把菜价从小到大排序,然后先不买最贵的,就买前面的,每次就是最多消费 (就相当于求                       他们的最大价值)。最后再减去最后一个最贵的。


#include<cstdio>
#include<cstring>
#define M 1000+10
#include<algorithm>
using namespace std;
int cost[M],f[M];
int main()
{
    int n,my;
    while(~scanf("%d",&n),n)
    {
        for(int i=1;i<=n;i++)
            scanf("%d",&cost[i]);
        scanf("%d",&my);
        sort(cost,cost+n+1);
        //for(int i=1;i<=n;i++)
             // printf("%d ",cost[i]);
              //printf("\n");
        if(my<5)
        {
            printf("%d\n",my);
            continue; //  小于五块他就不能购物。
        }
        else{
          memset(f,0,sizeof(f));
               for(int i=1;i<n;i++) // 这里不能到n 最贵的菜先不买
                    for(int j=my-5;j>=cost[i];j--)  //  这里要减去5  。保证最后剩一个大于五块的余额买最贵的菜
                        f[j]=max(f[j],f[j-cost[i]]+cost[i]);
        }
        printf("%d\n",my-f[my-5]-cost[n]);//  这里总钱数减去 最大消费和最贵的菜,是不是就是卡上剩钱最少
    }
    return 0;
}




目录
相关文章
|
数据采集 测试技术 API
python爬虫之Appium 的使用
搭建appium环境,appium基本使用,API操作等等
547 0
批处理 取得当前路径 %CD%
在DOS的批处理中,有时候需要知道当前的路径。在DOS中,有两个环境变量可以跟当前路径有关,一个是%cd%, 一个是%~dp0。      这两个变量的用法和代表的内容一般是不同的。     1.
1755 0
|
9月前
|
机器学习/深度学习 自然语言处理 数据安全/隐私保护
《解锁低资源语言NLP密码:创新技术与方法大揭秘》
在自然语言处理(NLP)领域,高资源语言如英语、中文取得了显著进展,但低资源语言因数据匮乏面临诸多挑战。为应对这一问题,研究者开发了多种创新技术:数据增强通过变换现有数据生成更多样本;预训练模型如mBERT迁移跨语言知识,降低对标注数据的依赖;多语言迁移学习借鉴相似语言的经验;半监督与无监督学习则挖掘未标注数据的价值。这些技术正逐步攻克低资源语言处理的难题,推动全球语言交流与理解。
221 2
|
12月前
CPU的原理
CPU的原理
500 1
|
存储 安全 编译器
|
IDE 前端开发 网络安全
JetBrains 远程开发的使用和心得
JetBrains 远程开发的使用和心得
739 0
|
JavaScript 前端开发 程序员
正则表达式
地狱-天堂之说,源自老程序员的话.老程序员告诉我们,没有正则表达式就像地狱一般,有了正则表达式我们就像进了天堂一样.好,我们下面看这么几个需求:   需求1:“192.168.10.5[port=8080]”,这个字符串表示IP地址为192.168.10.5的服务器的8080端口是打开的,请用程序解析此字符串,然后打印出“IP地址为***的服务器的***端口是打开的”。
1745 0
|
Shell Linux
linux下的rpm包的制作--以红旗2009开源大赛附加题为例
一、首先准备rpmbuild命令,采用yum install rpm-build -y特别注意:不是rpmbuild,而是rpm-build,用rpmbuild系统会提示你压根就没有这款软件。
1265 0