nyoj 791——Color the fence——————【贪心】
2024-08-27 18:56:02
Color the fence
时间限制:1000 ms | 内存限制:65535 KB
难度:2
- 描述
-
Tom has fallen in love with Mary. Now Tom wants to show his love and write a number on the fence opposite to
Mary’s house. Tom thinks that the larger the numbers is, the more chance to win Mary’s heart he has.
Unfortunately, Tom could only get V liters paint. He did the math and concluded that digit i requires ai liters paint.
Besides,Tom heard that Mary doesn’t like zero.That’s why Tom won’t use them in his number.
Help Tom find the maximum number he can write on the fence.
- 输入
- There are multiple test cases.
Each case the first line contains a nonnegative integer V(0≤V≤10^6).
The second line contains nine positive integers a1,a2,……,a9(1≤ai≤10^5). - 输出
- Printf the maximum number Tom can write on the fence. If he has too little paint for any digit, print -1.
- 样例输入
-
5
5 4 3 2 1 2 3 4 5
2
9 11 1 12 5 8 9 10 6 - 样例输出
-
55555
33 题意:给你一个v升油漆,给出数字1--9对应的油漆花费,让你用那么多油漆画出最大的数。 解题思路;/*
这题的贪心思想比较明显。我们要让能得到数尽量大,那么就要保证让位数尽量长,在位数
尽量长的基础上,让高位数尽量大,这是我们的贪心策略。我们知道,除以最小的数,可以
让位数最长,然而最长可以不仅仅是由最小的数得到。如:v=5 a={2,3,24,32,31,14,15,7,9},
虽然可以得到最长长度是2,且由除以2可得到结果11,但是最优的结果却是21。所以只要我们能
保证我们得到的高位数字比选择最小的数所得高位数字大并且位数相等即可。
*/#include<bits/stdc++.h>
using namespace std;
const int INF=1e9;
int digit[20];
int main(){
int n,i,v,j,k,minv,ai;
while(scanf("%d",&v)!=EOF){
minv=INF;
for(i=1;i<=9;i++){
scanf("%d",&digit[i]);
minv=minv>digit[i]?digit[i]:minv;
}
if(minv>v){
printf("-1\n");
continue;
}
for(i=v/minv;i>=1;i--){//目前的染料如果染最小花费那个数字可以染多少位
for(j=9;j>=1;j--){ //从大到小遍历数字
if(v>=digit[j]&&(v-digit[j])/minv+1>=i){
//目前的染料能染较大的数字且保证跟染最小那个数字可染的位数相同
//贪心选择染大的数字
printf("%d",j);
v-=digit[j];
}
}
}printf("\n");
}
return 0;
}
最新文章
- 转 jQuery 中bind(),live(),delegate(),on() 区别
- MapleSim助力长臂挖掘机建模问题解决
- 国际化支持(I18N)
- Mongodb Manual阅读笔记:CH7 索引
- 【apache】yum 安装Apache(Centos 6.5)
- Android OpenCV样例调试+报错处理
- 关于微信扫描二维码下载apk文件的细节设计
- Apache配置多端口多站点
- phpcms V9 首页模板文件解析(转)
- 【Cocos2d-x JavaScript Binding】
- JPDA 利用Eclipse和Tomcat进行远程调试 --转
- CSS制作出绚丽燃烧的火狐狸
- poj3280(区间dp)
- Turn the corner
- 为什么在Python里推荐使用多进程而不是多线程
- Web.config中设置启用webservice远程调试访问
- OpenGL执行渲染图片的主要操作步骤
- 统计字符串中字符出现的次数(||和&;&;的区别)
- linux下内核的配置和编译(2017-1-17)
- Django中需要注意的点