CF1257D Yet Another Monster Killing Problem 题解与代码

很蠢地在div2的D题卡住做不出来,这次的D题算是比较简单的,看了题解之后学会了一种新姿势---后缀修改数组,贪心新姿势!!

本题题意: 有n个怪物,每个怪物的power是ai

有 m个勇士,power是pi ,忍耐度是si

当勇士比当前怪物power小或忍耐度为0时结束一天,不然就继续。求最小天数。

题解:本题求最小天数,那可以试试用贪心思考该问题,因为每个英雄可以用无数次,我们考虑到肯定要用power大并且忍耐度大的勇士来杀怪

因此设置bst数组,bsti表示忍耐度大于等于i天的勇士的power最大是多少(后缀修改!!!)。这样就可以枚举怪物,随着天数的增长观察什么时候结束

我们设置当前没杀死的怪物坐标为npos ,cnt每次的初始值为0,代表用忍耐度大于cnt的英雄去杀怪(显然天数大的英雄能力值<=天数小的,因为能打一天不一定能打两天,能打两天的肯定能打一天)。

如果这个怪物能被杀死,那就npos++,一直到不能杀死的情况为止,注意的是,如果大于等于一天的英雄都不能杀死,那么无解。

CF1257D Yet Another Monster Killing Problem 题解与代码
#include<iostream>
#include<cstring>
#include<vector>
#include<cmath>
#include<string>
#define x first 
#define y  second 
using namespace std;
typedef long long ll;
const int N=2e5+10;
int bst[N];
int a[N];
int n,m;
int s[N];
int p[N];
int main(){
    int t;
    scanf("%d",&t);
    while(t--){scanf("%d",&n);
        for(int i = 0; i <= n; ++i) bst[i] = 0;
        
        int i;
        for(i=1;i<=n;i++){
            scanf("%d",&a[i]);
        }
        scanf("%d",&m);
        for(i=1;i<=m;i++){
           scanf("%d%d",&p[i],&s[i]);
           bst[s[i]]=max(bst[s[i]],p[i]);    
        }
        for(i=n-1;i>=1;i--){
            bst[i]=max(bst[i],bst[i+1]);
        }
        int res=0;
        int pos=1;
        bool ok=true;
        while(pos<=n){
            res++;
            int npos=pos;
            int mx=0;
            while(true){
                mx=max(mx,a[npos]);
                if(mx>bst[npos-pos+1]){
                    break;
                }
                npos++;
            }
            if(npos==pos){
                ok=false;
                break;
            }
            pos=npos;
        }
        if(ok==false)
        printf("-1\n");
        else
        printf("%d\n",res);
    }
}
View Code

 

上一篇:面试总结 | 百度 NLP 实习生


下一篇:二叉排序树查找递归 非递归