题解：CF1985F Final Boss

YZMX · 2024-06-12 15:55:12 · 题解

题目描述

给出 n 个攻击方式，每个攻击有伤害 a 和冷却 c。每回合可以任意使用不在冷却的攻击。敌人血量为 h。求最少多少回合可以打败敌人。

题目分析

如果使用常规优先队列等，我认为处理伤害时比较麻烦。如果使用二分答案，那么处理会比较简单。

当我们知道了回合，如何计算第 i 个攻击总共造成多少伤害？

由题目可知，第一回合一定可以造成一次伤害，那么假设经过 x 回合恰好使用了 n 次第 i 个攻击，可以得到 x =1 + (n-1) \times c_i。只有当 x 增加一个 c_i 时才会让攻击次数增加，所以下取整就能得到 x 回合之后用了几次攻击。

攻击次数 n = \lfloor \frac{ x + c_i - 1 }{ c_i } \rfloor。

代码

#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<map>
#include<vector>
#include<queue>
#define int unsigned long long
#define qwq ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pii pair<int,int>
using namespace std;

int t,n,h;
struct node{
    int a,c;
}e[200005];
bool check(int x){
    int res=0;
    for(int i=1;i<=n;i++){
        res+=((x-1+e[i].c)/e[i].c)*e[i].a;//计算
        //注意：如果不开unsigned long long 这里需要加上res>=h的判断
    }
    return res>=h;
}

signed main(){
    cin>>t;
    while(t--){
        cin>>h>>n;
        for(int i=1;i<=n;i++){
            cin>>e[i].a;
        }
        for(int i=1;i<=n;i++){
            cin>>e[i].c;
        }
        int l=0,r=4e14;//其实不用开这么大
        while(l<r){//二分
            int mid=(l+r-1)/2;
            if(check(mid)){
                r=mid;
            }else{
                l=mid+1;
            }
        }
        cout<<l<<endl;

    }

    return 0;
}