P1485 火枪打怪

巧妙地使用前缀和进行复杂度优化（其实是后缀，但反着做就是前缀了qwq）

题解：

很明显，对于p我们要进行二分答案，复杂度一只log

但这也意味着check函数复杂度只能为线性的，这就是问题的难度所在

首先，朴素地想，可以从右往左打怪，同时维护左边每个怪的剩余血量$b_i$，如果枚举到$i$时，$b_i<0$就说明它死了，否则就一直用子弹，知道$b_i<0$或子弹用光

因为p是相对固定的，所以可以先用sqrt()得出溅射的最远距离$s$

假设从左到右第i只怪原有血量为$a_i$，在$i$右边用了$m$次子弹，每次子弹直接作用在$x_j$位置上

可以得到计算式：$b_i=a_i-\sum\limits_{j=1}^{m}[p-(x_j-i)^2]$

尝试对它进行拆分：

发现对于此式需要维护三个东西：$m$，$\sum\limits_{j=1}^{m}x_j^2$，$\sum\limits_{j=1}^{m}x_j$

对于三者分别开一个记录后缀和的数组，每用一枚子弹，就更新一下

对于距离的限制，用后缀和简单差分一下即可

这样就可以做到$O(1)$ 查询，$O(n)$判断了

代码：

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    x=0;char c=getchar();bool f=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return  x;
}
template<class t> inline void write(t x){
    if(x<0){putchar('-'),write(-x);}
    else{if(x>9)write(x/10);putchar('0'+x%10);}
}

#define int long long

const int N=5e5+5;
int a[N],sum1[N],sum2[N],sum3[N],ans,n,k;

inline int min(const int &x,const int &y){return x<y?x:y;}
/*sum1[]是第三个，sum2[]是第二个，sum3[]是第一个*/
bool check(int p){
    int ma=sqrt(p); //预处理出最大距离
    for(int i=n;i>=1;i--){
        sum1[i]=sum1[i+1]; //继承
        sum2[i]=sum2[i+1];
        sum3[i]=sum3[i+1];
        int lim=min(n+1,i+ma+1);
        int hp=a[i]-(sum3[i]-sum3[lim])*(p-i*i); //从三个后缀和那分别查询
        hp+=sum2[i]-sum2[lim];
        hp-=2*i*(sum1[i]-sum1[lim]);
        if(hp<0) continue; //死了就跳过
        while(hp>=0){
            hp-=p;
            sum1[i]+=i; //分别维护三个后缀和
            sum2[i]+=i*i;
            sum3[i]++;
            if(sum3[i]>k) return 0; //没子弹了就失败
        }
    }
    return 1;
}

signed main(){
    read(n);read(k);
    for(int i=1;i<=n;i++) read(a[i]);
    int l=1,r=1e12;
    while(l<=r){
        int mid=l+r>>1;
        if(check(mid)) r=mid-1,ans=mid;
        else l=mid+1;
    }
    write(ans);
}
赏

fighter