Too Rich(贪心加搜索)
个人心得:10月份月赛题目,很low,就过了一道水题而且是把所有猜测都提交才过的。这段时间不知道忙什么去了,
也没怎么刷题感觉自己越来越差,还不如新来的大一学弟呢,别人起码天天刷代码到半夜,比起刚在区域赛拿银的学长们,
溜了溜了。慢慢磨练吧。
题目心得:这题意思很简单,就是用最多的硬币去负款,我比赛时是从正面开始的,发现自己low一是这样麻烦而且漏洞多,
后面看了题解他是从后面开始的。
要用尽量多的硬币凑P元钱,假设我现在硬币总共的面值和为M,那么换个思路,我现在要从总共的硬币中拿走尽量少的硬币,使剩下的硬币为P元。
那么问题转化成了,用尽量少的硬币去凑出M−P元,这个题目就有点熟悉了,不过这里有两个特殊的地方,一个是每种硬币都有数量限制,一个是面值大的硬币并不是面值小的硬币的整数倍。
假设没有数量限制,那么就是简单的贪心,尽量用面值大的硬币去凑出M−P元就好了。但是这个题用这个思路的话,会有这种情况。
假设现在有20,20,20,50这四个硬币,要去凑60元,如果以之前的思路贪心的话,那么是无解的,但是这里可以不用50元这个硬币,而用3个20元的去凑出60元。
那么对于这种情况,就要尝试一下,对于每种硬币,去掉一个这种硬币后的解。
题目:
For example, if p=17p=17 and you have two $10$10 coins, four $5$5 coins, and eight $1$1coins, you will pay it by two $5$5 coins and seven $1$1 coins. But this task is incredibly hard since you are too rich and the sticker is too expensive and pusheen is too lovely, please write a program to calculate the best solution.
InputThe first line contains an integer TT indicating the total number of test cases. Each test case is a line with 11 integers p,c1,c5,c10,c20,c50,c100,c200,c500,c1000,c2000p,c1,c5,c10,c20,c50,c100,c200,c500,c1000,c2000, specifying the price of the pusheen sticker, and the number of coins and banknotes in each denomination. The number cici means how many coins/banknotes in denominations of ii dollars in your wallet.
1≤T≤200001≤T≤20000
0≤p≤1090≤p≤109
0≤ci≤1000000≤ci≤100000OutputFor each test case, please output the maximum number of coins and/or banknotes he can pay for exactly pp dollars in a line. If you cannot pay for exactly pp dollars, please simply output '-1'.Sample Input
3
17 8 4 2 0 0 0 0 0 0 0
100 99 0 0 0 0 0 0 0 0 0
2015 9 8 7 6 5 4 3 2 1 0
Sample Output
9
-1
36
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iomanip>
#include<algorithm>
using namespace std;
const int maxn=;
long long ans=maxn;
int number[];
int next[]={,,,,,,,,,};
void dfs(int i,long long sum,long long t){
int next[]={,,,,,,,,,};
if(sum==){
ans=min(ans,t);
return ;
}
if(i<) return;
long long c=min((long long )number[i],sum/next[i]);
dfs(i-,sum-c*next[i],t+c);
if(c>)
{
c--;
dfs(i-,sum-c*next[i],t+c);
}
}
int main()
{ int t;
cin>>t;
int next[]={,,,,,,,,,};
while(t--){
long long p,q=;
ans=maxn;
int sum=;
cin>>p;
for(int i=;i<;i++){
cin>>number[i];
q+=number[i]*next[i];
sum+=number[i];
}
long long s=q-p;
if(s<)
{
cout<<-<<endl;
continue;
}
dfs(,s,);
if(ans==maxn)
cout<<-<<endl;
else cout<<sum-ans<<endl;
}
return ;
}
最新文章
- CSS3学习总结
- 类传奇手游简单Demo
- MySQL命令执行sql文件的两种方法
- 访谈将源代码的函数 strcpy/memcpy/atoi/kmp/quicksort
- CentOS系统安全配置
- javascript 匿名函数的理解,js括号中括function 如(function(){})
- 流媒体开发之-腾讯体育NBA视频点播解析
- 201521123005 《Java程序设计》 第十四周学习总结
- Nacos环境搭建
- Mysql基础之 事务
- feign client 的简单使用(1)
- swift杂记
- 使用npm国内镜像
- Assets.xcassets 应用
- 如何区分USB 2.0 和USB 3.0插口
- 解决 Windows 环境 Git Bash 无法识别 Composer 命令的问题
- 对于REST中无状态(stateless)的一点认识(转)
- web测试需要注意几个非常重要的测试点
- Hadoop伪分布安装详解(四)
- Eclipse 使用中遇到的一些问题!