京东技术岗笔试真题【星际快递】多语言题解

星际快递(C/Py/Java /Js/Go)题解京东技术岗 0314笔试 第一题题目内容星际快递公司有NNN个包裹需要派送每个包裹有两种派送方式常规派送消耗较多燃料虫洞派送使用一个虫洞通行证可以消耗较少燃料的情况下完成派送当前快递飞船携带了XXX单位的燃料和YYY张虫洞通行证。星际快递公司想要计算在优先派送尽可能多包裹的情况下最小的燃料消耗是多少请你帮助他们计算一下。输入描述第一行三个整数N,X,YN,X,YN,X,Y分别表示包裹数量携带燃料量以及通行证数量。接下来NNN行每行两个整数表示各个包裹常规派送和虫洞派送分别需要的燃料量。数据范围1≤N≤1001 ≤ N ≤ 1001≤N≤1001≤X≤50001 ≤ X ≤ 50001≤X≤50001≤Y≤501 ≤ Y ≤ 501≤Y≤50每个包裹常规派送和虫洞派送的燃料消耗均介于[1,50][1, 50][1,50]之间。输出描述一行两个整数空格分开表示最多可派送的包裹数量及对应的最小燃料消耗。样例1输入3 20 1 8 5 7 4 10 6输出2 12样例2输入4 25 2 10 6 8 5 12 7 9 6输出3 20题解和思路思路实现思路动态规划定义dp数组其中dp[i][j]表示完成j个运输使用k个通行费所需最小燃料。初始全部设置为不可达值额外定义dp[0][0] 1从前往后枚举运输任务从大到小枚举完成任务数 j 以及从大到小枚举通行证使用数 k如果dp[j][k]可达状态转移方程为常规配送dp[j 1][k] min(dp[j 1][k], dp[j][k] a);虫洞运输:dp[j 1][k 1] min(dp[j 1][k 1], dp[j][k] b);按照3的逻辑处理之后最终可以确定最大运输数量和使用燃料的数量。上述代码的时间复杂度为ON X YC#includebits/stdc.husingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intN,X,Y;cinNXY;vectorintA(N),B(N);for(inti0;iN;i){cinA[i]B[i];}// dp[j][k] 完成j个运输使用k个通行费所需最小燃料vectorvectorintdp(N1,vectorint(Y1,INT_MAX));dp[0][0]0;for(inti0;iN;i){intaA[i],bB[i];for(intjN-1;j0;j--){for(intkY;k0;k--){if(dp[j][k]INT_MAX){continue;}// 常规dp[j1][k]min(dp[j1][k],dp[j][k]a);// 冲动if(k1Y){dp[j1][k1]min(dp[j1][k1],dp[j][k]b);}}}}intbestCnt0,minFule0;for(intjN;j0;--j){intcurINT_MAX;for(intk0;kY;k)curmin(cur,dp[j][k]);if(curX){bestCntj;minFulecur;break;}}coutbestCnt minFuleendl;return0;}Javaimportjava.io.BufferedReader;importjava.io.IOException;importjava.io.InputStreamReader;importjava.util.StringTokenizer;publicclassMain{staticfinalintINFInteger.MAX_VALUE;publicstaticvoidmain(String[]args)throwsIOException{BufferedReaderbrnewBufferedReader(newInputStreamReader(System.in));StringTokenizerstnewStringTokenizer(br.readLine());intNInteger.parseInt(st.nextToken());intXInteger.parseInt(st.nextToken());intYInteger.parseInt(st.nextToken());int[]Anewint[N];int[]Bnewint[N];for(inti0;iN;i){stnewStringTokenizer(br.readLine());A[i]Integer.parseInt(st.nextToken());B[i]Integer.parseInt(st.nextToken());}// dp[j][k] 完成j个运算使用k个通行费所需最小燃料int[][]dpnewint[N1][Y1];for(inti0;iN;i){for(intj0;jY;j){dp[i][j]INF;}}dp[0][0]0;for(inti0;iN;i){intaA[i],bB[i];for(intjN-1;j0;j--){for(intkY;k0;k--){if(dp[j][k]INF){continue;}// 常规dp[j1][k]Math.min(dp[j1][k],dp[j][k]a);// 冲动if(k1Y){dp[j1][k1]Math.min(dp[j1][k1],dp[j][k]b);}}}}intbestCnt0,minFuel0;for(intjN;j0;j--){intcurINF;for(intk0;kY;k){curMath.min(cur,dp[j][k]);}if(curX){bestCntj;minFuelcur;break;}}System.out.println(bestCnt minFuel);}}pythonINFfloat(inf)N,X,Ymap(int,input().split())A[0]*N B[0]*Nforiinrange(N):A[i],B[i]map(int,input().split())# dp[j][k] 完成j个运算使用k个通行费所需最小燃料dp[[INF]*(Y1)for_inrange(N1)]dp[0][0]0foriinrange(N):a,bA[i],B[i]forjinrange(N-1,-1,-1):forkinrange(Y,-1,-1):ifdp[j][k]INF:continue# 常规dp[j1][k]min(dp[j1][k],dp[j][k]a)# 冲动ifk1Y:dp[j1][k1]min(dp[j1][k1],dp[j][k]b)bestCnt0minFuel0forjinrange(N,-1,-1):curmin(dp[j])ifcurX:bestCntj minFuelcurbreakprint(bestCnt,minFuel)Javascriptconstreadlinerequire(readline);constrlreadline.createInterface({input:process.stdin,output:process.stdout});constinput[];rl.on(line,line{input.push(line);});rl.on(close,(){letidx0;const[N,X,Y]input[idx].split( ).map(Number);constAnewArray(N);constBnewArray(N);for(leti0;iN;i){const[a,b]input[idx].split( ).map(Number);A[i]a;B[i]b;}// dp[j][k] 完成j个运算使用k个通行费所需最小燃料constdpArray.from({length:N1},()Array(Y1).fill(Number.MAX_SAFE_INTEGER));dp[0][0]0;for(leti0;iN;i){constaA[i],bB[i];for(letjN-1;j0;j--){for(letkY;k0;k--){if(dp[j][k]Number.MAX_SAFE_INTEGER){continue;}// 常规dp[j1][k]Math.min(dp[j1][k],dp[j][k]a);// 冲动if(k1Y){dp[j1][k1]Math.min(dp[j1][k1],dp[j][k]b);}}}}letbestCnt0;letminFuel0;for(letjN;j0;j--){letcurNumber.MAX_SAFE_INTEGER;for(letk0;kY;k){curMath.min(cur,dp[j][k]);}if(curX){bestCntj;minFuelcur;break;}}console.log(bestCnt minFuel);});Gopackagemainimport(bufiofmtmathos)funcmin(a,bint)int{ifab{returna}returnb}funcmain(){in:bufio.NewReader(os.Stdin)varN,X,Yintfmt.Fscan(in,N,X,Y)A:make([]int,N)B:make([]int,N)fori:0;iN;i{fmt.Fscan(in,A[i],B[i])}// dp[j][k] 完成j个运算使用k个通行费所需最小燃料dp:make([][]int,N1)fori:0;iN;i{dp[i]make([]int,Y1)forj:0;jY;j{dp[i][j]math.MaxInt32}}dp[0][0]0fori:0;iN;i{a,b:A[i],B[i]forj:N-1;j0;j--{fork:Y;k0;k--{ifdp[j][k]math.MaxInt32{continue}// 常规dp[j1][k]min(dp[j1][k],dp[j][k]a)// 冲动ifk1Y{dp[j1][k1]min(dp[j1][k1],dp[j][k]b)}}}}bestCnt:0minFuel:0forj:N;j0;j--{cur:math.MaxInt32fork:0;kY;k{curmin(cur,dp[j][k])}ifcurX{bestCntj minFuelcurbreak}}fmt.Println(bestCnt,minFuel)}