【题解】火枪打怪

法一.

法二.



法三.（本人的作死方法，调了一晚上）
x j = p − ( i − j ) 2 x_j=p-(i-j)^2 xj​=p−(i−j)2

x j + 1 = p − ( i − j − 1 ) 2 = p − ( i − j ) 2 − 1 + 2 ( i − j ) x_j+1=p-(i-j-1)^2=p-(i-j)^2-1+2(i-j) xj​+1=p−(i−j−1)2=p−(i−j)2−1+2(i−j)

x j = x j + 1 + ( 1 + 2 i ) − 2 j x_j=x_{j+1}+(1+2i)-2j xj​=xj+1​+(1+2i)−2j

推广一下：

x j = x j + 1 + s u m − t o t ∗ 2 j x_j=x_{j+1}+sum-tot*2j xj​=xj+1​+sum−tot∗2j

用sum维护1+2i，然后递推即可。

对于超出范围的部分，需要减去递推的增量，可以令$x[i-1-q]-=mid-(q+1)\ast (q+1)$。$sum$,$tot$部分减去所含增量即可。

#include
using namespace std;
const int N=5*1e5+5;long long n,k,a[N],b[N],x[N],y[N],der[N],der2[N];bool check(long long mid) {long long tot=0,sum=0,q=sqrt(mid);for(int i=1;i<=n+1;i++) x[i]=0,der[i]=0,der2[i]=0;for(int i=n;i>=1;i--) {x[i]=x[i]+x[i+1]-sum+(tot-der2[i+1])*2*i;b[i]=a[i]-x[i];sum-=der[i];der2[i]+=der2[i+1];if(b[i]>=0) {long long t=(b[i]-1)/mid+1;tot+=t,sum+=t*(2*i-1),x[i]+=t*mid;if(i-1-q>0) x[i-1-q]-=t*(mid-(q+1)*(q+1)),der[i-1-q]+=t*(2*i-1),der2[i-1-q]+=t;}}return tot<=k;
}int main() {scanf("%lld%lld",&n,&k);for(int i=1;i<=n;i++)scanf("%d",&a[i]);long long l=1,r=1e18,ans=0;while(l<=r) {long long mid=(l+r)>>1;if(check(mid)) r=mid-1,ans=mid;else l=mid+1;}printf("%lld",ans);
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！