阿里算法岗 0530笔试真题 - 荆棘林的最优砍断计划

荆棘林的最优砍断计划阿里算法岗 0530笔试 第一题题目内容林中共有n nn株荆棘第i ii株的坚硬度为a i a_iai​宝刀的初始锋利度为K KK。拉布可以选择任意数量的荆棘每株至多尝试一次并以任意顺序依次尝试砍断。每次尝试遵循以下规则若当前锋利度K KK满足K ≥ a i K \ge a_iK≥ai​则该荆棘被成功砍断。无论成功与否每次尝试结束后锋利度K KK都会永久减少1 11。拉布可以放弃任意荆棘放弃不消耗锋利度。请计算在最优策略下最多能成功砍断多少株荆棘。输入描述每个测试文件包含多组测试数据。第一行输入一个整数T TT1 ≤ T ≤ 10 5 1 \le T \le 10^51≤T≤105表示数据组数每组测试数据描述如下每组输入一行两个整数n , K n, Kn,K1 ≤ n ≤ 2 × 10 5 1 \le n \le 2 \times 10^51≤n≤2×1051 ≤ K ≤ 10 9 1 \le K \le 10^91≤K≤109。接下来一行输入n nn个整数a 1 , a 2 , … , a n a_1, a_2, \dots, a_na1​,a2​,…,an​1 ≤ a i ≤ 10 9 1 \le a_i \le 10^91≤ai​≤109。保证所有测试数据的n nn之和不超过2 × 10 5 2 \times 10^52×105。输出描述对于每组测试数据输出一个整数表示在最优策略下最多能成功砍断的荆棘数量。样例1输入3 5 5 2 1 4 10 3 2 1 10 10 3 3 3 3 3输出4 0 1题解和思路思路实现思路贪心按照优先砍锋利度高的能砍就砍的策略去计算数量。将荆棘降序排序从大到小进行扫描如果a[i] k,更新ans, k--最终ans就是能砍的最大数量。C#includebits/stdc.husingnamespacestd;intmain(){ios_base::sync_with_stdio(false);cin.tie(nullptr);intT;cinT;while(T--){intn,k;cinnk;vectorinta(n);for(inti0;in;i){cina[i];}// 排序sort(a.begin(),a.end());intcount0;for(intin-1;i0;i--){// 能砍断就砍if(a[i]k){k--;count;}}coutcountendl;}return0;}Javaimportjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){ScannerscnewScanner(System.in);intTsc.nextInt();while(T--0){intnsc.nextInt();intksc.nextInt();int[]anewint[n];for(inti0;in;i){a[i]sc.nextInt();}// 排序Arrays.sort(a);intcount0;for(intin-1;i0;i--){// 能砍断就砍if(a[i]k){k--;count;}}System.out.println(count);}sc.close();}}pythonTint(input())for_inrange(T):n,kmap(int,input().split())alist(map(int,input().split()))# 排序a.sort()count0foriinrange(n-1,-1,-1):# 能砍断就砍ifa[i]k:k-1count1print(count)print(count)Javascriptconstreadlinerequire(readline);constrlreadline.createInterface({input:process.stdin,output:process.stdout});constlines[];rl.on(line,line{lines.push(line);});rl.on(close,(){letidx0;constTNumber(lines[idx]);for(lett0;tT;t){const[n,k0]lines[idx].split( ).map(Number);letkk0;constalines[idx].split( ).map(Number);// 排序a.sort((a,b)a-b);letcount0;for(letin-1;i0;i--){// 能砍断就砍if(a[i]k){k--;count;}}console.log(count);}});Gopackagemainimport(fmtsort)funcmain(){varTintfmt.Scan(T)forT0{T--varn,kintfmt.Scan(n,k)a:make([]int,n)fori:0;in;i{fmt.Scan(a[i])}// 排序sort.Ints(a)count:0fori:n-1;i0;i--{// 能砍断就砍ifa[i]k{k--count}}fmt.Println(count)}}