cf B. Color the Fence

http://codeforces.com/contest/349/problem/B
贪心
 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 const int inf=1<<30;
 6 
 7 int a[10];
 8 int v,k;
 9 int main()
10 {
11     while(scanf("%d",&v)!=EOF)
12     {
13         int min1=inf;
14         k=0;
15         for(int i=1; i<=9; i++)
16         {
17             scanf("%d",&a[i]);
18             if(a[i]<min1)
19             {
20                 min1=a[i];
21                 k=i;
22             }
23             else if(a[i]==min1&&k<i)
24             {
25                 k=i;
26             }
27         }
28         if(v<min1)
29         {
30             printf("-1
");
31             continue;
32         }
33         if(v%min1==0)
34         {
35             int m=v/min1;
36             for(int i=1; i<=m; i++)
37             {
38                 printf("%d",k);
39             }
40             printf("
");
41         }
42         else
43         {
44             int len=v/min1;
45             for(int j=len; j>=1; j--)
46             {
47                 for(int i=9; i>=1; i--)
48                 {
49                     int x=v-a[i];
50                     if(x<0) continue;
51                     if(x/min1==j-1)
52                     {
53                         printf("%d",i);
54                         v-=a[i];
55                         break;
56                     }
57                 }
58             }
59             printf("
");
60         }
61     }
62     return 0;
63 }
View Code