荆棘林的最优砍断计划

阿里算法岗 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 TT（1 ≤ T ≤ 10 5 1 \le T \le 10^51≤T≤105）表示数据组数，每组测试数据描述如下：
每组输入一行两个整数n , K n, Kn,K（1 ≤ n ≤ 2 × 10 5 1 \le n \le 2 \times 10^51≤n≤2×105，1 ≤ 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

题解和思路

思路

实现思路：贪心

1. 按照优先砍锋利度高的，能砍就砍的策略去计算数量。
2. 将荆棘降序排序，从大到小进行扫描，如果a[i] <= k,更新ans++, k--
3. 最终ans就是能砍的最大数量。

C++

#include<bits/stdc++.h>usingnamespacestd;intmain(){ios_base::sync_with_stdio(false);cin.tie(nullptr);intT;cin>>T;while(T--){intn,k;cin>>n>>k;vector<int>a(n);for(inti=0;i<n;i++){cin>>a[i];}// 排序sort(a.begin(),a.end());intcount=0;for(inti=n-1;i>=0;i--){// 能砍断就砍if(a[i]<=k){k--;count++;}}cout<<count<<endl;}return0;}

Java

importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);intT=sc.nextInt();while(T-->0){intn=sc.nextInt();intk=sc.nextInt();int[]a=newint[n];for(inti=0;i<n;i++){a[i]=sc.nextInt();}// 排序Arrays.sort(a);intcount=0;for(inti=n-1;i>=0;i--){// 能砍断就砍if(a[i]<=k){k--;count++;}}System.out.println(count);}sc.close();}}

python

T=int(input())for_inrange(T):n,k=map(int,input().split())a=list(map(int,input().split()))# 排序a.sort()count=0foriinrange(n-1,-1,-1):# 能砍断就砍ifa[i]<=k:k-=1count+=1print(count)print(count)

Javascript

constreadline=require('readline');constrl=readline.createInterface({input:process.stdin,output:process.stdout});constlines=[];rl.on('line',line=>{lines.push(line);});rl.on('close',()=>{letidx=0;constT=Number(lines[idx++]);for(lett=0;t<T;t++){const[n,k0]=lines[idx++].split(' ').map(Number);letk=k0;consta=lines[idx++].split(' ').map(Number);// 排序a.sort((a,b)=>a-b);letcount=0;for(leti=n-1;i>=0;i--){// 能砍断就砍if(a[i]<=k){k--;count++;}}console.log(count);}});

Go

packagemainimport("fmt""sort")funcmain(){varTintfmt.Scan(&T)forT>0{T--varn,kintfmt.Scan(&n,&k)a:=make([]int,n)fori:=0;i<n;i++{fmt.Scan(&a[i])}// 排序sort.Ints(a)count:=0fori:=n-1;i>=0;i--{// 能砍断就砍ifa[i]<=k{k--count++}}fmt.Println(count)}}