洛谷 P1485 火枪打怪

题目描述

LXL进入到了一片丛林,结果他发现有n只怪物排成一排站在他面前。LXL有一杆火枪能对付这些怪物。他知道从左至右数第i只怪物的血量是mi。现在LXL可以将一些子弹射向某个怪物。LXL可以控制他所发射的子弹数量及子弹的威力值。当某个子弹射到第i个怪物，如果这个子弹的威力值为p，除了这个怪物会掉p点血以外，它左边的第j个怪物(j<i)，也会遭到Max(0, p - (i - j) * (i - j))的溅射伤害（好神奇的子弹）。当某只怪物的血量小于0时，它就死了，但它的尸体还在，即怪物的位置永远不会改变。LXL希望只用k发子弹，请你求出一个最小的正整数p，使LXL用k发子弹且每发子弹的威力值为p就可以消灭所有怪物。

SOL

我们显然可以发现这道题的二分性质。再细心观摩一波数据，50W，只能用O（nlogn）及以下的算法。二分需要一个log，这便要求我们O(n)处理check函数。

比较显然，我们可以差分。我们发现只有右边对左边有贡献，不妨从右到左做，我们发现这是一个二次多项式，那么可以二阶差分，对于单一的子弹来说，他的

伤害的差分是一个等差数列，K=2n-1，那对差分数组进行差分，我们统计对当前怪物有贡献的子弹，那么这个伤害的二阶差分就是两倍的子弹数。那么我们还

有一个问题，那就是子弹的伤害不可能是负数。我们有这样一个方法，我们在一颗子弹的伤害区域的最左侧打标记  -1，标示该位置之后出子弹范围，那么我们同

时在一阶差分数组中把多余的伤害减掉，那么这颗子弹之后就没有贡献了。

#include<bits/stdc++.h>

#define sight(c) ('0'<=c&&c<='9')

#define LL long long

inline void read(int &x) {

    static char c;

    for (;!sight(c);c=getchar());

    for (x=;sight(c);c=getchar())x=x*+c-;

}

inline void read(long long &x) {

    static char c;static int b;

    for (b=;!sight(c);c=getchar())if (c=='-') b=-;

    for (x=;sight(c);c=getchar())x=x*+c-;

    x*=b;

}

#define N 501007

#define min(a,b) (a)<(b)?(a):(b)

#define HP a

LL len,ans2,ans,Ans,cm,n,dle,a[N],k,r,c1[N],c2[N],c3[N],c4[N],hp[N];

bool check(LL P)

{

    int sss=sqrt(P); int tot=;

    LL t1=,t2=,t3=,t0=;

    memset(c1,,sizeof(c1)); memset(c2,,sizeof(c2));

    memset(c3,,sizeof(c3)); memset(c4,,sizeof(c4));

    for(int i=;i<=n;++i)hp[n-i+]=HP[i]+;//记得+1，因为怪物0血还没有死

    for(int i=;i<=n;++i)

    {

        t3+=c3[i]; t2+=c2[i];

        t1+=c1[i]+t2; t0+=t1+c4[i];

        hp[i]-=1ll*P*t3-t0;

        if(hp[i]<=)continue; int gg=((hp[i]+P-)/P);

        tot+=gg; if(tot>k)return false;

        c3[i+]+=gg;c3[min(n+,i+sss+)]-=gg;

        c2[i+]+=1ll**gg;c2[min(n+,i+sss+)]-=*gg;

        c1[i+]-=gg;c1[min(n+,i+sss+)]-=1ll*(1ll**sss-)*gg;

        c4[min(n+,i+sss+)]-=1ll*sss*sss*gg;

    }

    return tot<=k;

}

int main () {

    read(n); read(k);

    for (int i=;i<=n;i++) read(a[i]);

    r=1ll<<;

    while (r) {

        if (!check(ans+r)) ans+=r;

        r>>=;

    }

    printf("%lld\n",ans+); return ;

}