Description
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就可以消灭所有怪物。
solution
正解：二分答案 朴素做法从后往前扫，因为右边的点不能依赖左边的点的溅射伤害，所以如果还剩下血量必须得打掉，然后计算对左边的溅射伤害，计算溅射伤害是 \(\sqrt(n)\) 的，考虑优化这个地方，伤害的式子是 \[p-(i-j)^2\]\[p-(i^2-2*i*j+j^2)\] 拆开之后非常好维护，这是一个 移动一个\(sqrt(n)\) 的窗口的过程，我们只需要维护窗口中的数的数量和 \(j^2\) 和 \(j\) 的和即可，可以 \(O(1)\) 求出当前剩余的血量
#include#include #include #include #include #include #include #include #define RG register#define il inline#define Min(a,b) ((a)<(b)?(a):(b))#define Max(a,b) ((a)>(b)?(a):(b))using namespace std;typedef long long ll;const int N=500005;int n,K;ll a[N],c[N];il bool check(ll mid){ ll tmp,ret=0,xy; RG int i; memset(c,0,sizeof(c)); int block=sqrt(mid)+1; ll xif=0,cnt=0,xi=0; for(i=n;i>=1;i--){ if(i+block<=n && c[i+block]>0){ tmp=i+block; xif-=c[tmp]*tmp*tmp; cnt-=c[tmp]; xi-=c[tmp]*tmp; } tmp=mid*cnt-cnt*i*i+2*xi*i-xif; tmp=a[i]-tmp; if(tmp>0){ xy=(tmp+mid-1)/mid; xif+=xy*i*i; xi+=xy*i; cnt+=xy; ret+=xy; c[i]=xy; } if(ret>K)return 0; } return ret<=K;}void work(){ ll l=1,r=2e14,mid,ans=0; scanf("%d%d",&n,&K); for(int i=1;i<=n;i++)scanf("%lld",&a[i]),a[i]++; while(l<=r){ mid=(l+r)>>1; if(check(mid))ans=mid,r=mid-1; else l=mid+1; } printf("%lld\n",ans);}int main(){ work(); return 0;}