6.25atcoderabc257e - addition and multiplication 2

Title Description

link

AtCoderABC257E - Addition and Multiplication 2

A word description

E - Addition and Multiplication 2 /
Time Limit: 2 sec / Memory Limit: 1024 MB

Score : 500 points

Problem Statement
Takahashi has an integer x. Initially, x=0.

Takahashi may do the following operation any number of times.

Choose an integer i (1≤i≤9). Pay C
i
​
yen (the currency in Japan) to replace x with 10x+i.
Takahashi has a budget of N yen. Find the maximum possible value of the final x resulting from operations without exceeding the budget.

Constraints
1≤N≤10
6

1≤C
i
​
≤N
All values in input are integers.
Input
Input is given from Standard Input in the following format:

N
C
1
​
C
2
​
… C
9
​

Output
Print the answer.

Sample Input 1
Copy
5
5 4 3 3 2 5 3 5 3
Sample Output 1
Copy
95
For example, the operations where i=9 and i=5 in this order change x as:

0→9→95.

The amount of money required for these operations is C
9
​
+C
5
​
=3+2=5 yen, which does not exceed the budget. Since we can prove that we cannot make an integer greater than or equal to 96 without exceeding the budget, the answer is 95.

Sample Input 2
Copy
20
1 1 1 1 1 1 1 1 1
Sample Output 2
Copy
99999999999999999999
Note that the answer may not fit into a 64-bit integer type.

Topic analysis

1. This question wants to maximize the number , Maximum first guarantee The number of digits is the largest , That is, use the smallest number to k The value divided by rounding down is , The digit length of the maximum number .
2. On the basis of the largest number of digits , Make sure the first place is as big as possible , But it can not affect the length of digits .（ Classic greed ）
3. Thus, it is proposed to select the largest one from the first place each time , Judge the condition ： When we get this one, we can fill in the minimum for the rest to ensure the positioning （ The number is the same ）.

Code implementation

#include<bits/stdc++.h>
using namespace std;

int k,mi=1e9,n;
int a[100];
int main(){
    
	scanf("%d",&k);
	for(int i=1;i<=9;i++){
    
		scanf("%d",&a[i]);
		mi=min(mi,a[i]);
	}
	n=k/mi;
	for(int i=1;i<=n;i++){
    
		for(int j=9;j>=1;j--){
    
			if(k-a[j]>=mi*(n-i)){
    
				k-=a[j];
				printf("%d",j);
				break;
			}
		}
	}
	printf("\n");
	return 0;
}