本文主要是介绍2019杭电多校第八场 HDU 6685 Rikka with Coin(思维)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6685
题目思路：蓝瘦，居然这么简单..QAQ wa到自闭
10分硬币最多用一个，因为用了俩可以用20分代替
20分硬币最多仨，因为俩不够，对40 60这个样例，用仨20是最省的，四个又不够优秀，四个的话10 20 20 50能凑出更多的数字
50分硬币最多一个，俩可以用1美元代替
这些结论都在赛场推出来了，结果一美元处理的不对凉了QAQ
直接i j k枚举前三种硬币，然后枚举这三种硬币下，是否每个物品都可以只用1美元就能凑整，可以的话取需要最多美元的那个人的需求量+i+j+k，就行了。其实就是在确定i j k的情况下再枚举需要的一美元最少数量就行了
以下是代码：
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
const int MAXN = 2e5+5;
int a[MAXN];
int t,n;
int check(int ii,int jj,int kk){int flag=0,maxx=-1;rep(p,1,n){int flagg=1e9+7;rep(i,0,ii){rep(j,0,jj){rep(k,0,kk){if((a[p]-i*10-j*20-k*50)%100==0){flagg=min(flagg,(a[p]-i*10-j*20-k*50)/100);}}}}if(flagg==1e9+7)return -1;maxx=max(maxx,flagg);}return maxx;
}
int main()
{scanf("%d",&t);while(t--){scanf("%d",&n);rep(i,1,n)scanf("%d",&a[i]);int ans=1e9+7;rep(i,0,1){rep(j,0,3){rep(k,0,1){int temp=check(i,j,k);if(temp!=-1){ans=min(ans,i+j+k+temp);}}}}if(ans==1e9+7){puts("-1");continue;}printf("%d\n",ans);}return 0;
}
这篇关于2019杭电多校第八场 HDU 6685 Rikka with Coin(思维)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
