首页 > 试题广场 > 击败魔物
[编程题]击败魔物
  • 热度指数:605 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
薯队长来到了迷宫的尽头,面前出现了N只魔物,Hi表示第i只魔物的血量,薯队长需要在T个回合内击败所有魔物才能获胜。每个回合薯队长可 以选择物理攻击一只魔物,对其造成1点伤害(物理攻击次数无上限);        或者消耗1点法力释放必杀技对其造成固定X点伤害(薯队长开始拥有M 点法力)。问X至少多大,薯队长才有机会获胜;如果无论如何都无法在T回合内获胜,则输出-1 

输入描述:
第一行三个整数分别表示:N,T,M 第二行有N个整数:H1,H2,H3...HN 


输出描述:
输出一个整数,表示必杀技一次最少造成多少固定伤害 
示例1

输入

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

考察点:二分搜索、贪心
参考了@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())
发表于 2020-07-06 22:33:53 回复(0)
java100%case通过代码如下:
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;
        }
    }
}



发表于 2020-08-21 17:37:16 回复(0)

[编程题]击败魔物 小红书 二分查找

我们把问题分解成两个子问题:

1.已知 必杀技伤害X 验证能否获胜
2.二分查找能够获胜的最小伤害X

考虑二分查找的上下边界:

  • 平A即可取胜,此时为X的下界0
  • 技能秒杀任意怪,此时为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)
}
发表于 2020-06-14 15:29:52 回复(0)
贡献个C++版本的吧。
#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;
}


发表于 2020-09-06 16:17:40 回复(0)
通过率50%,让人自闭
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
}


发表于 2020-07-29 23:43:55 回复(0)
二分查找答案,检查回合数之类能不能杀掉所有怪物,可以用大根堆对怪物血量进行排序,用魔法优先干掉堆顶的,如果还有剩余的血在插入堆里面
发表于 2020-07-19 20:53:23 回复(0)