技术标签： 算法 面试 c语言 贪心算法 2018中南大学机试题
猪年快乐！在这个快乐的日子里我们当然要去超市买可乐喝啦!
现在超市有n种可乐，第 i 种可乐的价格为C[i] ，体积为 2i-1 毫升，每种可乐都是无限供应的 ，现在你想买至少 L毫升的可乐 ，作为一个省钱小能手，聪明的你能够想到最少要花多少钱吗?
输入包含多组测试用例。
每组测试用例第一行包含两个数字 n 和 L (1 ≤ n ≤ 30; 1 ≤ L ≤ 109) ， n是可乐的种类数， L是我们最终要买的可乐体积。
第二行包含 n 个数字 C1，C2,…Cn n (1 ≤ ci ≤ 109) ,代表每一种可乐的价格。
输出一个数字 ， 购买至少L毫升的可乐需要的最少花费。
4 12
20 30 70 90
4 3
10000 1000 100 10
4 3
10 100 1000 10000
150
10
30
这道题第一眼看上去有点像完全背包问题，仔细思考之后就会发现还是有不同的地方，背包问题的背包空间大小是确定的。但是这道题没有说不可以多买可乐，求至少购买L毫升，也可以比L毫升多也行。这题是用贪心去做。肯定是买物美价廉的东西。先把每种可乐的每毫升单价算出来，一开始就买单价小的买，如果需要购买的可乐体积比这种可乐的体积小。这有两种情况可以选择，一是选择直接再买一瓶这种可乐，多了体积也没关系只要价钱低就好，第二种在剩下可乐中购买剩下体积的可乐，那种方法的钱少就用那种方法。（这题要用long long去做,用int会溢出）
上代码
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
long long L, V[32], cost[32];
int n;
int vis[32];
int in[32];
double c[32];
bool cmp(int a, int b)
{
if(c[a] < c[b]) return true;
else return false;
}
long long tanxin(long long l)
{
long long an, tem;
for(int i = 0; i < n; i++)
{
if(vis[in[i]])
{
continue;
}
if(l % V[in[i]] == 0)
{
an = (l / V[in[i]]) * cost[in[i]];
return an;
}
else
{
an = (l / V[in[i]]) * cost[in[i]];
vis[in[i]] = 1;
tem = tanxin(l - (l / V[in[i]]) * V[in[i]]);
if( tem > cost[in[i]] )
an = an + cost[in[i]];
else
an = an + tem;
return an;
}
}
}
int main()
{
V[0] = 1;
for(int i = 1; i < 32; i++)
V[i] = V[i-1]*2;
while(scanf("%d %lld", &n, &L) != EOF)
{
for(int i = 0; i < n; i++)
{
scanf("%lld", &cost[i]);
c[i] = cost[i]*1.0/V[i];
in[i] = i;
}
sort(in, in+n, cmp);
memset(vis, 0, sizeof(vis));
printf("%lld\n", tanxin(L));
}
return 0;
}
文章浏览阅读1.4w次，点赞5次，收藏52次。https://mp.weixin.qq.com/s/FtIhKiENv483iHE053RPkg当前，人工智能发展借助深度学习技术突破得到了全面关注和助力推动，各国政府高度重视、资本热潮仍在加码，各界对其成为发展热点也达成了共识。本文旨在分析深度学习技术现状，研判深度学习发展趋势，并针对我国的技术水平提出发展建议。一、深度学习技术现状深度学习是本轮人工智能爆发的关键技术。..._深度学习方法、模型的发展趋势
文章浏览阅读1.7w次，点赞8次，收藏17次。比如字典：my_dict = { "first_key": 'first_value', "second_key": "second_value", "third_key": "third_value",}如果使用：print(my_dict.keys()[0])print(my_dict.values()[0])这会导致报错：TypeError: 'dict_keys' object is not subscriptableTypeError: 'dict_va_python dict 取第一个值
文章浏览阅读2.4k次。文章目录前言案例解读读取数据文本文件excel文件数据库jsonDataFrame构造根据字典根据numpy构造根据列表构造属性方法四则运算转换前言工作了一段时间，天天写sql，玩linux上的脚本；已经快忘记python怎么写了，pandas忘记的更是干净，便打算写一写博客来复习一下pandas的API。案例解读读取数据文本文件 ''' Flat file 平面文件->文..._panda datafram
文章浏览阅读223次。一 安装依赖和环境 1 安装依赖（第二个如果找不到包可以不装）# yum group install 'Development Tools'# yum install redhat-lsb kernel-abi-whitelists# yum install kernel-devel-$(uname -r) 2 建立rpmbuild环境（注意不要使用root账..._centos7 43142网卡驱动
文章浏览阅读4.8k次。建立PlayService服务package com.iwanghang.drmplayer;import android.app.Service;import android.content.Intent;import android.media.MediaPlayer;import android.net.Uri;import android.os.Binder;impo_android.net.uri 设置网络歌曲
文章浏览阅读1w次，点赞4次，收藏7次。突如其来的错误花费了些时间搭建的VMware渗透测试主机，今天打开突然出现了这个情况！！error：打不开文件“D:\testwin10\Windows 10渗透-000002.vmdk”: 系统找不到指定的文件。如下图所示网上找了很多的方案但是并没能正确的解决。问题所在根据提示是文件出现了问题。可以看到是我这里少了一个文件导致的这个问题。毕竟这是用来做安全的一台虚机，所以我猜测应该是被Windows Defender给删除了，然而我一开始并没有发现并且彻底删除了这个文件。。。。。所以如_找不到windows server 2012 r2 datacenter-cl1-000001.vmkd文件怎么办
文章浏览阅读1.6k次。不借助应用程序，使用系统命令，进行串口功能测试_ttys5
文章浏览阅读928次，点赞15次，收藏26次。文章目录web前端期末大作业 (1500套) 集合一、网页介绍二、网页集合三、作品演示A电影主题B漫画主题C商城主题D家乡主题E旅游主题F餐饮/美食主题G环境主题H游戏主题I 个人主题K体育主题L博客主题M汽车主题N文化主题P美妆主题Q企业主题R教育主题S其他主题更多源码web前端期末大作业 (1500套) 集合临近期末，大一新生的各种考试和专业结课作业纷至沓来。web实训大作业、网页期末作业、web课程与设计、网页设计等，简直让人头大。你还在为网页设计老师的作业要求感到头大？网页作业无从下手？_大学生web网页设计实例
文章浏览阅读1k次。原文出自：https://blog.csdn.net/weixin_41182157/article/details/83041109感谢网友的分享！！！linux中装软件的特点linux中安装软件比windows中复杂。linux中安装软件一般有以下几种方法：第一种：在线安装。譬如ubuntu中使用apt-get install vim来安装vim软件。第二种：自己下载安装包来安装。这..._bash: /home/ubuntu/cross-tool/arm-2009q3/bin/arm-none-linux-gnueabi-gcc-4.4.
文章浏览阅读900次。当我们进行开发的时候，总会后把依赖的名字写错的情况，但是maven依旧尝试去下载，但是这个下载下来的依赖无法使用，并且有些时候进行开发的时候还会对程序造成一定的影响，所以我们需要删除这些无效的依赖。这是我的配置，我的maven仓库在D:\APP\maven3.8.8\maven_repository下。可以通过以下代码一键删除，将此内容复制到文本文件，然后将后缀名改为.bat，保存后双击该文件。如果一个文件一个文件的找，那么太花费时间，而且还不一定能全部找出来。_maven删除无用依赖
文章浏览阅读175次。选择器{ 样式; }标签选择器：html代码中的标签类选择器：类选器名称{ css样式代码 } 使用方法：1.<span>小米</span> 2.<span class= "stress">小米</span> 3. <style> .str..._慕课网css背景和列表2-6
文章浏览阅读1.6k次。-------下面的文字只是记录一下想法，想看答案的可以忽略所有文字，直接按照下面图片上的步骤去操作-------------闲暇时间会玩一玩游戏，比如LOL，一来可以歇歇脑，让本就不多的头发得以延长寿命，二来还可以体验一下不一样的世界。虽然不是什么大手子，但是偶尔也会有狂拽炫酷吊炸天的时刻，这时候总希望把这些精彩时刻保存下来，分享出去，LOL为了满足玩家的需求增加了这个功能，本来是很好的事，但..._英雄时刻我为什么录制好了 然后结束视频怎么就剩下十几秒是怎么回事