首先要使用TreeSet存储 需要注意到其底层是在维护红黑树,如果一个个插入,那么就需要一次次进行树的结构调整,所花费的时间会比较长,会被卡,所以可以进行优化,先将值存入HashSet中,再一次性批量加入,那么只需建图一次。
TreeSet
import java.util.*;
import java.io.*;
public class Main{
static int n;
static long w;
static int[] arr;
static int k;
static TreeSet<Integer> weight=new TreeSet<Integer>();
static Set<Integer> set=new HashSet();
static int res=0;
static void bfs1(int idx,int s){
if(idx>=k){
set.add(s);
return;
}
bfs1(idx+1,s);
if((long)s+arr[idx]<=w){
bfs1(idx+1,s+arr[idx]);
}
}
static void bfs2(int idx,int s){
if(idx>=n){
int m=weight.floor((int)(w-s));
res=Math.max(res,s+m);
return;
}
bfs2(idx+1,s);
if((long)arr[idx]+s<=w) bfs2(idx+1,s+arr[idx]);
}
public static void main(String[] args)throws Exception{
BufferedReader read=new BufferedReader(new InputStreamReader(System.in));
String[] s=read.readLine().split(" ");
w=Long.valueOf(s[0]);
n=Integer.valueOf(s[1]);
set.add(0);
arr=new int[n+1];
for(int i=0;i<n;i++){
arr[i]=Integer.valueOf(read.readLine());
}
k=n/2+2;
bfs1(0,0);
weight.addAll(set);
bfs2(k,0);
System.out.println(res);
}
}
大佬,我java一直被卡时间
可能是数据变了,你的代码过不去了....
Orz不过让我学到了treeset
把n/2+2换成n/2