第一题写一个sql语法分析,分析出sql中的表名,临时表不算,按最简单的sql输出了一下,11%
第二题商旅问题感觉是最优子集问题,前两天leetcode有类似的,穷举ac了,第二题默认输出-1都有27%的用例通过
第二题暴力ac
public class Main { static ArrayList<List<Integer>> plans = new ArrayList<>(); public static void main(String[] args) { int res = -1; Scanner sc = new Scanner(System.in); //权益数 int n = Integer.parseInt(sc.nextLine()); String packagesIn = sc.nextLine(); String[] s = packagesIn.split(" "); ArrayList<List<Integer>> packageList = new ArrayList<>(); //填充权益包 for(String string:s){ String[] vArray = string.split(","); ArrayList<Integer> vList = new ArrayList<>(); for(String v:vArray){ vList.add(Integer.parseInt(v)); } packageList.add(vList); } int packageNum = s.length; int[] price = new int[packageNum]; String priceIn = sc.nextLine(); String[] ps = priceIn.split(" "); for(int i=0;i<packageNum;i++){ price[i] = Integer.parseInt(ps[i]); } String valuesIn = sc.nextLine(); String[] vs = valuesIn.split(" "); int[] values = new int[vs.length]; for(int i=0;i<vs.length;i++){ values[i] = Integer.parseInt(vs[i]); } //先穷举吧 dfs(false,0,packageList,new ArrayList<Integer>(),values); if(plans.size()>0){ for (List<Integer> plan : plans) { int jiage = 0; for (int p : plan) { jiage += price[p]; } if (res == -1) { res = jiage; } else { res = Math.min(res, jiage); } } } //先测测有多少-1用例嘿嘿 System.out.println(res); } public static void dfs(boolean choosePre,int cur,List<List<Integer>> packageList,List<Integer> curChoose,int[] values){ if(cur == packageList.size()){ boolean allFind = !(curChoose.size()==0); for(int value:values){ boolean find = false; for(int i=0;i<curChoose.size();i++){ int pIndex = curChoose.get(i); List<Integer> quanyiList = packageList.get(pIndex); for(int quanyi:quanyiList){ if(quanyi==value){ find=true; break; } } if(find){ break; }else if(i==curChoose.size()-1){ allFind=false; } } } //全部符合,加入计划 if(allFind){ plans.add(new ArrayList<Integer>(curChoose)); } return; } dfs(false, cur + 1, packageList,curChoose,values); curChoose.add(cur); dfs(true,cur + 1, packageList,curChoose,values); curChoose.remove(curChoose.size()-1); } }
全部评论
(13) 回帖