349B - Color the Fence (贪心)

时间:2022-12-17 23:29:49

本题的意思是:用油漆写数字,数字的范围是(1--9)

每次都输入9个数,每个位上的数代表写这个数所需要的油漆量。

先找到写一个数所消耗最小的油漆量。则n=m/min;表示所能写的最大位数;

然后从最大的位数9开始查找,要想写下此值要满足两个条件;

一是:m大于等于a[j];

二是:不影响能写的最大位数,一定的保证最大位数不变;

 

 

 

#include"stdio.h"
#include"string.h"
#define mm 99999999
int main()
{
 int m,n,i,j,min;
 int a[36];
 while(scanf("%d",&m)!=EOF)
 {
  min=mm;
  for(i=1;i<=9;i++)
  {
   scanf("%d",&a[i]);
   if(a[i]<min)
    min=a[i];
  }
  if(min>m)
  {
   printf("-1\n");
   continue;
  }
  n=m/min;
  for(i=n;i>=1;i--)
  {
   for(j=9;j>=1;j--)
   {
    if(m>=a[j]&&(m-a[j])/min>=i-1)
    {
     printf("%d",j);
     m=m-a[j];
     break;
    }
   }
  }
  printf("\n");
 }
 return 0;
}