第一行三个整数分别表示:N,T,M 第二行有N个整数:H1,H2,H3...HN
输出一个整数,表示必杀技一次最少造成多少固定伤害
3 4 3 5 2 1
3
对于50%的数据: 0<N<10^3 0<T<10^3 0<=M<=T 0<Hi<10^4
对于100%的数据 0<N<10^5 0<T<10^5 0<=M<=T 0<Hi<10^7
import java.util.*; public class Main{ public static void main(String[] args){ Scanner in = new Scanner(System.in); int n = in.nextInt(); int t = in.nextInt(); int m = in.nextInt(); Integer[] h = new Integer[n]; int maxH=0,totalH=0; //获取怪物血量输入,顺便找出最大怪物血量,顺便计算怪物总血量。 for (int i=0;i<h.length;i++){ int s = in.nextInt(); h[i] = s; maxH=Math.max(maxH,s); totalH+=s; } //如果怪物总血量小于回合数,说明平A就能解决所有怪物,所以必杀技伤害为最低0 if(totalH<=t){ System.out.println(0); return; } //把怪物的血量从大到小排序 Arrays.sort(h,Collections.reverseOrder()); /*从2到最大怪兽血量maxH,进行升序循环判断,找到第一个伤害就是,最低必杀技伤害 Q:为什么从2开始?A:因为普工伤害为1,必杀技小于等于普工伤害时,都使用普工解决就可以 */ for (int i=2;i<=maxH;i++){ //判断该必杀技伤害是否能够通关 if(dfs(h,t,m,i,totalH)){ System.out.println(i); return; } } System.out.println(-1); } public static boolean dfs(Integer[] h,int t,int m,int x,int totalH){ //判断回合数是否大于蓝量 if(t>m){ //看所有蓝量用完后再在回合内使用普工时,所能造成的总血量是否大于怪物总血量,如果不行,则无法通关 if(t-m+m*x>=totalH){ /** 怪物血量大于必杀技伤害的,每一个都使用必杀技,确保必杀技伤害不溢出。 **/ Integer[] ht = Arrays.copyOf(h,h.length); int j=0; for(int i=0;i<h.length&&m>0&&h[i]>=x;i++){ int st = h[i]/x; int sx = h[i]%x; if(st<=m){ ht[i] = sx; totalH -= st*x; m-=st; t-=st; }else{ ht[i] -= m*x; totalH -= m*x; m=0; t-=m; } } //如果必杀技使用完毕,则只能进行平砍,判断怪物总剩余血量是否小于等于剩余回合数就行 if(m==0){ return totalH<=t-m; }else { //如果必杀技未使用完毕,则直接对剩余血量最多的怪再次使用必杀技,确保必杀技利益最大化。 //怪物剩余血量再排序 Arrays.sort(ht, Collections.reverseOrder()); //由于java最后10%的案例超时,所以判断了一下剩余蓝量是否大于怪物数量的一半 if(m>ht.length/2){ //如果超过一半,则只需计算另外一半未死的怪物血量就是剩余怪物总血量 totalH = 0; for (int i = m; i < ht.length; i++) { totalH += ht[i]; } }else { //如果没有超过一半,则每一只怪死掉后,总血量减去该怪物的剩余血量就行 for (int i = 0; i < m; i++) { totalH -= ht[i]; } } //通过以上步骤算出怪物剩余总血量,如果小于使用全部技能后的回合数,就能平A通关了,如果不行则不能进行通关操作 return totalH <= t - m; } }else{ return false; } }else{ //如果回合数小于等于蓝量,则全程使用必杀技,看是否通关。 //直接回合数*必杀技看是否大于怪物总血量 return t*x>=totalH; } } }
考察点:二分搜索、贪心
参考了@Cyan1956大佬的代码,python实现
[0,max_hp]
的范围搜索最合适的伤害值,注意对一些特殊情形的处理。 check_valid
判断当前技能伤害能否过关def check_valid(num, turn, magic, hps, damage): # 使用技能造成伤害但不补刀,最后剩下法力值的时候在进行补刀 i = 0 for i in range(num): # 释放技能的次数为整除的次数或者是魔力值的次数,取小的那个 spell_time = min(hps[i] // damage, magic) hps[i] -= spell_time * damage turn -= spell_time magic -= spell_time if magic == 0: break # 去除刚好整除的值 hps = sorted(hps) i = 0 if hps[-1] == 0:return True while hps[i] == 0: i += 1 hps = hps[i:] # 普攻或者技能能够清掉 if sum(hps) <= turn : return True if len(hps) <= magic: return True # 还剩余法力值,此时怪物的血量必定都小于技能伤害,按血量从高到低使用技能 else: last = len(hps) - 1 while magic > 0: last -= 1 magic -= 1 turn -= 1 # 无法力值,判断能否用普攻清完 hps = hps[:last+1] return turn >= sum(hps) def main(): num, turn, magic = list(map(int, input().split())) hps = list(map(int, input().split())) #回合不够必定输 if len(hps) > turn: return -1 # 法力值为零且血量和大于回合数 必定输 if magic == 0 and sum(hps) > turn: return -1 left, right = 0, int(max(hps)) while left < right: mid = (left + right) // 2 # 注意python浅拷贝的坑 if check_valid(num, turn, magic, hps.copy(), damage=mid): right = mid else: left = mid+1 # 如果left = max(hps),同样是不存在伤害值满足条件,left一直右移直到越界 return left if left < max(hps) else -1 print(main())
我们把问题分解成两个子问题:
1.已知 必杀技伤害X 验证能否获胜
2.二分查找能够获胜的最小伤害X
考虑二分查找的上下边界:
package main import ( "fmt" "sort" ) //求和 func sum(arr []int) (ans int) { for _,v:=range arr{ ans+=v } return } //求较小值 func min(i,j int) int { if i<j{ return i }else{ return j } } //验证能否获胜 func f(ohs []int,n,t,m,x int) bool { hs:=make([]int, len(ohs)) copy(hs,ohs) for i,v:=range hs{ d:=min(v/x,m) hs[i]-=d*x m-=d t-=d if m==0{ break } } sort.Ints(hs) i:=0 for ;hs[i]==0;i++{} hs=hs[i:] if len(hs)==0{ return true } n= len(hs) if n<=m{ return true }else{ hs=hs[:n-m] t-=m return t>=sum(hs) } } func main() { var n,t,m,h int //回合数小于怪物数,必失败 if t<n{ fmt.Println(-1) return } //法力值大于回合数时多的也没用 if m>t{ m=t } //获取怪物血量 var hs []int fmt.Scan(&n,&t,&m) for i:=0;i<n;i++{ fmt.Scan(&h) hs = append(hs, h) } //平A取胜 if t>sum(hs){ fmt.Println(0) return } sort.Ints(hs) //二分查找 l,r:=0,hs[len(hs)-1] if !f(hs,n,t,m,r){ fmt.Println(-1) return } for l<r-1{ mid:=(l+r)/2 if f(hs,n,t,m,mid){ r=mid }else{ l=mid } } fmt.Println(r) }
#include<bits/stdc++.h> using namespace std; bool check(vector<int> &H,int x,int T,int M) { vector<int> help(H.begin(),H.end()); sort(help.begin(),help.end(),greater<int>()); for(auto &num:help) { int a=min(num/x,M); T-=a; M-=a; num-=a*x; if(M==0) break; } int sum=accumulate(help.begin(),help.end(),0); if(M==0 && T>=sum) return true; if(M==0 && T<sum) return false; sort(help.begin(),help.end(),greater<int>()); for(auto &num:help) { M--; T--; num=0; if(M==0) break; } sum=accumulate(help.begin(),help.end(),0); if(T>=sum) return true; else return false; } int main() { int N,T,M; while(cin>>N>>T>>M) { vector<int> H(N); int num; int maxv=INT_MIN,minv=INT_MAX; for(int i=0;i<N;i++) { cin>>num; maxv=max(maxv,num); minv=min(minv,num); H[i]=num; } int sum=accumulate(H.begin(),H.end(),0); if((minv>=1 && N>T) ||(sum>T && M==0)) {//回合数不足 或者 没有法力值 必然失败 cout<<-1<<endl; continue; } if(maxv==1 && N<=T) {//平A获胜 cout<<0<<endl; continue; } //M=min(M,T); int l=0,r=maxv; while(l<r) {//二分搜索答案 int x=(r+l)/2; if(check(H,x,T,M)) r=x; else l=x+1; } if(l==maxv) cout<<-1<<endl; else cout<<l<<endl; } return 0; }
const a = readline().split(' '), round_sum = parseInt(a[1]), mana = parseInt(a[2]), bloods = toInt(readline().split(' ')) print(killMonster(bloods, round_sum, mana)) function killMonster(bloods, round_sum, mana) { const monster_sum = bloods.length if (round_sum < monster_sum) { return -1 } let min = 0, max = Math.max.apply(null, bloods) if (checkDamage(bloods, round_sum, mana, min)) { return min } if (!checkDamage(bloods, round_sum, mana, max)) { return -1 } while ((max - min) >= 2) { const middle = Math.floor((max - min) / 2) + min if (checkDamage(bloods, round_sum, mana, middle)) { max = middle } else { min = middle } } return max } function checkDamage(bloods, round_sum, mana, damage) { const blood_sum = bloods.length let bloods_table = getTable(bloods) if (damage > 1) { while (mana > 0) { const info = damageDone(bloods_table, damage, blood_sum, mana) if (!info) { break } bloods_table = info[0] mana -= info[1] round_sum -= info[1] } } if (round_sum >= add(bloods_table)) { return true } else { return false } } function getTable(bloods) { let table = [] for (let blood of bloods) { if (table[blood]) { table[blood] += 1 } else { table[blood] = 1 } } return table } function damageDone(bloods_table, damage, blood_sum, mana) { if (bloods_table[0] == blood_sum) { return false } for (let i = bloods_table.length - 1; i > 0; i--) { if (bloods_table[i]) { const times = Math.floor(i / damage) == 0 ? 1 : Math.floor(i / damage) bloods_table[i] -= 1 const add_index = times < mana ? i - damage * times : (i - damage < 0 ? 0 : i - damage) if (bloods_table[add_index]) { bloods_table[add_index] += 1 } else { bloods_table[add_index] = 1 } return [bloods_table, times] } } return false } function add(table) { let sum = 0 for (let i = 1; i < table.length; i++) { if (table[i]) { sum += i * table[i] } } return sum } function toInt(like_arr) { for (let i = 0; i < like_arr.length; i++) { like_arr[i] = parseInt(like_arr[i]) } return like_arr }
#include<bits/stdc++.h> using namespace std; const long long MAXN = 1e+5 + 10; const long long MAXT = 1e+5 + 10; vector<long long> H(MAXN); bool solve(vector<long long>& H, long long X, long long T, long long N, long long M){ vector<long long> nums; long long sum_ = 0; // 第一轮进行让法力伤害打满 for(int i = 0;i < N;i++){ if(N - i > T) return false; int h = H[i]; if(h == 1) T -= 1; else{ if(M && X){ int atack_times = min(h / X, M); h -= X * atack_times; M -= atack_times; T -= atack_times; } if(h){ nums.push_back(h); sum_ += h; } } } // 第二轮先使用法力值 sort(nums.begin(), nums.end()); N = nums.size(); int i = N; while(M>0 && i){ if(i <= M) return true; if(sum_ <= T) return true; sum_ -= nums[i-1]; T -= 1; i -= 1; M -= 1; } // 再考虑普攻 return sum_ <= T; } int main(){ ios::sync_with_stdio(0),cin.tie(0); long long N,T,M; while(cin >> N >> T >> M){ if(T < N){ cout << -1 << endl; continue; } long long ans_l = 0; long long ans_r = 0; for(long long i = 0;i < N;i++){ cin >> H[i]; ans_r = max(ans_r, H[i]); } long long ans = -1; while(ans_l <= ans_r){ long long ans_m = ans_l + (ans_r - ans_l) / 2; if(solve(H,ans_m,T, N,M)){ ans = ans_m; ans_r = ans_m - 1; } else ans_l = ans_m + 1; } cout << ans << endl; } return 0; }
import java.io.*; import java.math.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { solve(); pw.close(); } public static void solve() throws IOException { int n = nextInt(); int t = nextInt(); int m = nextInt(); int[] a = new int[n]; for (int i = 0; i < n; i++) a[i] = nextInt(); int sum = Arrays.stream(a).sum(); if (t >= sum) { pw.println(0); return; } int l = 1, r = Arrays.stream(a).max().getAsInt(); while (l < r) { int mid = l + r >> 1; if (check(a, n, t, m, mid)) r = mid; else l = mid + 1; } pw.println(check(a, n, t, m, r) ? r : -1); } public static boolean check(int[] a, int n, int t, int m, int x) { PriorityQueue<Integer> q = new PriorityQueue<>(new Comparator<Integer>() { @Override public int compare(Integer o1, Integer o2) { return o2 - o1; } }); for (int v : a) { int cnt = Math.min(v / x, m); int rest = v - cnt * x; m -= cnt; t -= cnt; if (rest != 0) q.add(rest); if (t < 0) return false; } while (!q.isEmpty()) { int v = q.poll(); if (m > 0) { t--; m--; } else { t -= v; } if (t < 0) return false; } return true; } static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); static PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out))); static StringTokenizer tokenizer = new StringTokenizer(""); public static String next() throws IOException { while (!tokenizer.hasMoreTokens()) { tokenizer = new StringTokenizer(reader.readLine()); } return tokenizer.nextToken(); } public static int nextInt() throws IOException { return Integer.parseInt(next()); } }
let str1 = readline().split(" ") let n = Number(str1[0]); let time = Number(str1[1]); let attackNum = Number(str1[2]); let arr = readline().split(" ").map(x=>Number(x)) let allBlood = arr.reduce((pre,next)=>pre+next) function fn(arr,time,supperAttack,attackNum,len){ //所有怪物剩余血量 let s = allBlood let myarr = [...arr] //剩最多血量的怪物的血量 let max = 0 let maxIndex = -1 //回合数 while(time>0){ max = Math.max(...myarr) //如果最多血量的怪物血量都小于等于0,则证明怪物全打死了 if(max<=0){ return true } maxIndex = myarr.indexOf(max) //优先用法攻,优先打血量大的怪,目的是为了法攻能充分发挥作用 if(attackNum>0){ max = max - supperAttack attackNum-- s = s - supperAttack }else{ //法攻用完了,但所有怪物血量仍大于回合数,则打不完了 if(s>time){ return false } max = max - 1 s-- } myarr[maxIndex] = max time-- } } function fn2(n,time,attackNum,arr){ let max = Math.max(...arr) let left = 0 let right = max //要是法攻能做到一次秒一只还不能打完也没必要打了 if(!fn(arr,time,right,attackNum,n)){ print(-1) return } //记录最后一次可以打完怪的法攻伤害 let f = -1 while(left<=right){ let mid = Math.floor(left + (right-left)/2) //print(mid) let tag = fn(arr,time,mid,attackNum,n) //print(tag) if(tag){ f = mid right = mid - 1 }else( left = mid + 1 ) } if(f==-1){ print(-1) }else{ print(f) } return } fn2(n,time,attackNum,arr)
let arr = readline().split(' ').map(item => Number(item)); let N = arr[0]; let T = arr[1]; let M = arr[2]; let H = readline().split(' ').map(item => Number(item)); let maxH = Math.max(...H); let min = Infinity; let totalH = H.reduce((pre,i) => pre+i); if(T < H.length) print(-1); else if(T === totalH) print(0); else{ let l = 2; //必杀为1和为0时结果相同,所以只取0,已经判断过 let r = maxH; while(l <= r){ let mid = parseInt((l+r)/2); if(beat(mid,T,M,H,totalH)){ min = Math.min(min, mid); r = mid - 1; } else l = mid + 1; } if(min === Infinity)print(-1); else print(min); function beat(x,T,M,H, totalH){ let hp = Array.from(H); hp.sort((a,b) => b-a); if(T - M + M * x < totalH)return false; else{ //先把血量高的用必杀打到血量低于一次必杀的值 for(let i = 0; i<hp.length && M>0; i++){ if(hp[i]>=x){ hp[i] -= x; T --; M --; i --; } } hp.sort((a,b) => b-a); if(M >= hp.length) return true; //如果必杀次数足够肯定能成功 //如果必杀次数不够,用必杀消灭掉血量高的,剩下的判断用普攻能否消灭 hp = hp.slice(M); totalH = hp.reduce((pre,i) => pre+i); if(T - M >= totalH)return true; else return false; } } }
package main import ( "fmt" "sort" ) func main() { //第一行三个整数 N T M 怪物数量 回合数 魔法量 //第二行N个整数 代表每个怪物的血量 //1 获得输入数据 //2 遍历一遍 获得最大的怪物血量 或者直接排序 取最大的怪物血量作为固定伤害的上限 //3 一个回合值 先用魔法 用完之后还有参与血量加入数组里 再原数组里操作 切片切掉 如果还有血量就再添加进去 魔法没了之后 检测剩下的血量之和是否小于回合数 不是返回false n, t, m := 0, 0, 0 fmt.Scan(&n, &t, &m) data := make([]int, n) for i := range data { fmt.Scan(&data[i]) } sort.Ints(data[:]) maxBlood := data[len(data)-1] //存一个回合值 //fight ... fight := func(damage int) bool { Tdata := make([]int, n) round := 0 //限制为t magic := 0 //限制为m copy(Tdata, data) for i := n - 1; i > -1; i-- { round += Tdata[i] / damage //不浪费魔法的前提下 先用固伤灌满伤害 魔法输出几次就给回合数加几 magic = round Tdata[i] = Tdata[i] % damage //计算遭遇魔法后的血量 //如果回合耗尽 返回false if round > t { return false } if magic > m { //首先把多打的血还回去 然后跳出循环 round -= (magic - m) Tdata[i] += damage * (magic - m) break } } //走到这一步 说明对怪物造成了一轮魔法伤害或者魔法用完了 if magic > m { //说明魔法用完了 sum := 0 for i := 0; i < n; i++ { sum += Tdata[i] } if sum+round > t { return false } } else { //魔法没用完 接着用魔法打 sort.Ints(Tdata) for i := n - 1; magic < m && i > -1; magic++ { Tdata[i] = 0 round++ i-- if round > t { return false } } //走到这说明 回合没用完 魔法用完了 sum := 0 for i := 0; i < n; i++ { sum += Tdata[i] } if sum+round > t { return false } } return true } // for i := 2; i <= maxBlood; i++ { // if fight(i) { // fmt.Println(i) // return // } // } // fmt.Println(-1) //直接从小遍历 超时 因此改用2分法 left, right := 2, maxBlood for right > left { mid := (left + right) / 2 if fight(mid) { right = mid } else { left = mid + 1 } } if right == maxBlood { fmt.Println(-1) return } fmt.Println(right) }竟然没有用GO的,不用二分法 可以过60%的例子, 其他的超时了