博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
NYOJ-Color the fence
阅读量:7238 次
发布时间:2019-06-29

本文共 4205 字,大约阅读时间需要 14 分钟。

题目链接:http://acm.nyist.net/JudgeOnline/problem.php?pid=791

转载自:http://www.cnblogs.com/windysai/p/3432414.html

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

题目意思:给定v升的颜料和9个需要花费ad 升的颜料,花费ad 升的颜料意味着得到第d个数字,现在要求在所有的花费不超过v升的情况下,使得这些数字组合起来是最大的。

         一开始直接从最小花费的颜料着手,如果花费的颜料是相同的,就转到从d(也就是位数)最大贪心。这样测试9就开始卡住了。

         受到乌冬兄的指点迷津,终于有了思路,陆陆续续改了很多次,终于过了。以下摘自他的语录,白话文,大家请谅解:

      稳用颜料最少,最大的数字,先保证位数最长,然后再将剩余颜料从大数字开始贪心

      因为要数最大,所以根据“数”的比较顺序:

1。比较位数
2。从高位开始比较

     从数字比较的方法,推出贪心既思路

     由于本人悟性太低,下面是更详细的解说:

   1、先稳到用最小颜料既数字d,假设它价值为c

   2、先构造出s = v div c个d,求出剩余颜料r = v mod c
   3、从最高位扫描s,从大到小枚举可替换数字d' >= d,假设价值为c':若c'-c <= r,则替换当前位置的d为d', r -= c' - c
   4、最后得出替换后的s, s'即为所求
   注意:价值即一个数字要使用的颜料量

1 #include 
2 #include
3 #include
4 #include
5 #include
6 using namespace std; 7 8 const int maxn = 1e6 + 5; 9 struct paint10 { 11 int index; // 数字12 int num; // 该数字所花费的颜料量13 } a[maxn], b[maxn];14 15 int s[maxn]; // 用于保存结果16 17 int cmp(paint a, paint b)18 {19 if (a.num != b.num) // 先保证用的颜料量最少20 return a.num < b.num;21 return a.index > b.index; // 再保证数字最大22 }23 24 int main()25 {26 int i, j, v, tmp, t1;27 while (scanf("%d", &v) != EOF)28 {29 // freopen("in.txt", "r", stdin);30 for (i = 1; i <= 9; i++)31 {32 a[i].index = i;33 scanf("%d", &a[i].num);34 b[i].index = i; //b用于保存未排序前的序列,以便下面从大数字开始枚举35 b[i].num = a[i].num;36 }37 sort(a+1, a+10, cmp);38 if (v < a[1].num) // v比最少花费的颜料更少39 printf("-1\n");40 else41 { 42 tmp = v / a[1].num; // 得出最大位数43 if (v % a[1].num == 0) // 如果刚好可以除尽,最大的数就是tmp个a[1].num的数。44 {45 for (i = 0; i < tmp; i++)46 printf("%d", a[1].index);47 printf("\n");48 }49 else50 {51 for (i = 0; i < tmp; i++)52 {53 s[i] = a[1].index; // 先得出目前来说最长的数字,但可能不是最终结果54 }55 int r = v % a[1].num; // 余数56 t1 = r;57 for (i = 0; i < tmp; i++)58 { 59 for (j = 9; j >= 1; j--) // 从最大的位数开始枚举60 {61 if (b[j].num - a[1].num <= r && a[1].index < b[j].index) // 没有超过余数且数字比原来的排列数字的位数要大62 {63 s[i] = b[j].index;64 r = r - (b[j].num - a[1].num); // 余数要有所减少65 break;66 }67 }68 }69 if (t1 == r) // 如果根本没有可替换的数,那么就和刚好除尽的是同一种情况70 {71 for (i = 0; i < tmp; i++)72 printf("%d", a[1].index);73 printf("\n");74 }75 else76 {77 for (i = 0; i < tmp; i++) // 否则有替换的就输出新的最大数字78 {79 printf("%d", s[i]);80 }81 printf("\n");82 } 83 }84 }85 } 86 return 0;87 }

 

转载于:https://www.cnblogs.com/yfs123456/p/5674206.html

你可能感兴趣的文章
Android绑定远程服务
查看>>
LibSVM学习(二)——第一次体验libSvm
查看>>
linux下查看用户及用户组的方法
查看>>
C-遍历二叉树
查看>>
bean的生命周期
查看>>
mysql数据库的基本操作
查看>>
iOS-自定义Alert框
查看>>
LVS四种负载均衡类型,十种调度方法
查看>>
数据持久化之SQLite
查看>>
android4.1+ ListView 不滚动
查看>>
3. 类
查看>>
Axure快速创建原型的示例
查看>>
ssh连接错误的解决办法
查看>>
mac 下面wireshark 找不到网卡
查看>>
我的友情链接
查看>>
Python 6.3 文档测试
查看>>
mysteel Sql
查看>>
Dockerfile中的权限问题及工作目录问题(USER WORKDIR)
查看>>
c#文件读取和写入的方式总结
查看>>
Djano XSS的转义
查看>>