首页 > 代码库 > P4747 D’s problem(d)

P4747 D’s problem(d)

时间: 1000ms / 空间: 655360KiB / Java类名: Main

背景

冬令营入学测试题

描述

题目描述

         小D是一名魔法师,它最喜欢干的事就是对批判记者了。

         这次记者招待会上,记者对于小D的数学很好奇。于是小D找了个方法把记者批判了一番。

         它对记者抛出了这么一个问题:我有n点能量,写下数字i(1<=i<=9)需要花费a{i}点能量,我用这n点能量最多能写出什么数来?(当然可以不用光n点能量,具体看样例)

         记者们一脸懵逼,于是来求助于你。

输入格式

一行10个数,表示n,a1,a2,a3,…,a9。

输出格式

一个数表示答案。

备注

输入样例1

10 2 2 1 2 2 2 2 2 2

 

输出样例1

3333333333

 

输入样例2

10 4 11 11 11 11 11 11 11 10

 

输出样例2

11    

 

数据范围

对于30%的数据n,ai<=10。

对于60%的数据n,ai<=100。

对于100% 的数据1<=n,ai<=1000000,n>=min{ai}。

 

 1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 using namespace std; 5  6 const int INF=0x7fffffff; 7  8 int n,t,minn=INF; 9 int ans[10],a[10];10 11 int main()12 {13     scanf("%d",&n);14     for(int i=1;i<10;i++)15     {16         scanf("%d",&a[i]);17         if((a[i]<minn)||(a[i]==minn&&i>t))18         {19             minn=a[i];20             t=i;21         }22     }23     ans[t]=n/minn;24     n%=minn;25     for(int i=9;i>t;i--)26     {27         while(n+minn>=a[i])28         {29             ans[t]--;30             ans[i]++;31             n=n+minn-a[i];32         }33     }34     for(int i=9;i>=1;i--)35         for(int j=1;j<=ans[i];j++)36             printf("%d",i);37     return 0;38 }

 

P4747 D’s problem(d)