欢迎访问 生活随笔！
TAG聚合

生活随笔

当前位置： 首页 > 编程资源 > 编程问答 >内容正文

编程问答

nyoj 791 Color the fence(贪心)

发布时间：2025/3/16 编程问答 40 豆豆
生活随笔 收集整理的这篇文章主要介绍了 nyoj 791 Color the fence(贪心) 小编觉得挺不错的,现在分享给大家,帮大家做个参考.

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.
样例输入
55 4 3 2 1 2 3 4 529 11 1 12 5 8 9 10 6
样例输出
5555533


解题思路：

首先要肯定一点，数字位数越多，肯定会越大。所以这里可以采用贪心的思想，假设最小的颜料的用量为min，那么最长的位数可以达到V / min，接下来我们就枚举每一位可能的数字即可。这里还需要考虑，取了某一个数后，剩下的是否还可以保证最大。。

#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; int a[10]; int main() {int n;while(~scanf("%d", &n)){int Min = 0x3f3f3f3f;for(int i = 1; i < 10; i++){scanf("%d", &a[i]);Min = min(Min, a[i]);}if(n < Min){puts("-1");continue;}for(int i = n/Min-1; i >= 0; i--){for(int j = 9; j > 0; j--){if(n >= a[j] && (n - a[j])/Min >= i) //保证去了j之，还可以最长。。{printf("%d", j);n -= a[j];break;}}}puts("");}return 0; }

总结

以上是生活随笔为你收集整理的nyoj 791 Color the fence(贪心)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。