【链接】 我是链接,点我呀:)
【题意】
让你组成一个只由1~9组成的数字
每个数字需要的paint数字给定。
让你组成一个最大的数字,且所有数字的paint的总和不超过v.
【题解】
先求出a中的最小值mi
最后的长度显然就是a/mi啦
然后从高位到低位,优先让高位优先选择大的数字就好.
(判断这一位能否为i的条件就是,后面的所有位置全都选择mi
看看会不会超过剩余的paint数量就好
【代码】
import java.io.*;
import java.util.*;
public class Main {
static InputReader in;
static PrintWriter out;
public static void main(String[] args) throws IOException{
//InputStream ins = new FileInputStream("E:\\rush.txt");
InputStream ins = System.in;
in = new InputReader(ins);
out = new PrintWriter(System.out);
//code start from here
new Task().solve(in, out);
out.close();
}
static int N = 10;
static int L = (int)1e6;
static class Task{
int v,mi;
int a[],b[];
public void dfs(int dep,int rest) {
if (dep==0) return;
for (int i = 9;i >= 1;i--) {
if (rest-a[i]-(dep-1)*mi>=0) {
b[dep] = i;
dfs(dep-1,rest-a[i]);
return;
}
}
}
public void solve(InputReader in,PrintWriter out) {
a = new int[N+10];
b = new int[L+10];
v = in.nextInt();
for (int i = 1;i <= 9;i++) a[i] = in.nextInt();
mi = a[1];
for (int i = 1;i <= 9;i++) mi = Math.min(a[i], mi);
int len = v/mi;
if (len==0)
out.println(-1);
else {
dfs(len,v);
for (int i = len;i >= 1;i--) out.print(b[i]);
}
}
}
static class InputReader{
public BufferedReader br;
public StringTokenizer tokenizer;
public InputReader(InputStream ins) {
br = new BufferedReader(new InputStreamReader(ins));
tokenizer = null;
}
public String next(){
while (tokenizer==null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(br.readLine());
}catch(IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
}
}