Color the fence

朴灿烈づ我的快乐病毒、 2022-05-31 00:14 144阅读 0赞

## 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

来源

[CodeForce][]

上传者

[TC\_李远航][TC]

题意：给你一定体积的油漆，再给你一些数字用油漆写出来所需要的体积，问能写出来的最大数字是多少

思路：贪心算法，，，，

代码：

#include<stack>
    #include<queue>
    #include<math.h>
    #include<stdio.h>
    #include<string.h>
    #include<algorithm>
    using namespace std;
    int a[11];
    int main()
    {
        int v;
        while(scanf("%d",&v)!=EOF)
        {
            int i,j,q=0,ans=999999999;
            for(i=1; i<=9; i++)
            {
                scanf("%d",&a[i]);
                if(a[i]<ans)
                {
                    ans=a[i];
                }
            }
            if(v<ans)//连最小的都不够
            {
                printf("-1\n");
                continue;
            }
            q=v/ans;
            while(1)
            {
                for(i=9; i>=1; i--)
                {
                    if(v<a[i])//不能粉刷跳过
                        continue;
                    if(((v-a[i])/ans)>=(q-1))//贪心核心，从大往小筛选，一旦后面的大数能达到maxl这么长，毫无疑问这就是最大，如果都达不到这么长，毫无疑问，一开始的maxl就是最大值，数位长必然大
                    {
                        printf("%d",i);
                        v=v-a[i];
                        q--;
                        break;
                    }
                }
                if(q==0)
                    break;
            }
            printf("\n");
        }
        return 0;
    }

[CodeForce]: http://acm.nyist.edu.cn/JudgeOnline/search_result.php?source=CodeForce
[TC]: http://acm.nyist.edu.cn/JudgeOnline/profile.php?userid=TC_%E6%9D%8E%E8%BF%9C%E8%88%AA