题解

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
typedef long long ll;
ll l=1,r=1e14;
ll n,k,mid,ans;
ll Hp[500003],num[500003];
bool check(ll p)
{
ll over=(ll)sqrt(p)+1;//溅射范围
ll cnt=0;//子弹放置总个数
memset(num,0,sizeof(num));
ll plus=0,i=0,i2=0;
//plus表示有效子弹的个数，i表示放置子弹的位置，i2表示i^2
for(ll j=n;j>=1;j--)
{
if(num[j+1])//累加子弹的个数
{
plus+=num[j+1];
i+=num[j+1](j+1);
i2+=num[j+1](j+1)(j+1);
}
if((j+over<=n)&&(num[j+over]))//删除无效子弹的个数
{
plus-=num[j+over];
i-=num[j+over](j+over);
i2-=num[j+over](j+over)(j+over);
}
ll allhurt=1llplusp-1lljjplus+2lli*j-i2;//计算总伤害
if(Hp[j]>=allhurt)//如果不能直接杀死
{
num[j]=(Hp[j]-allhurt)/p+1;
cnt+=num[j];//累加总放置子弹的个数
}
if(cnt>k) return false;//如果放置子弹多余要求子弹个数
}
return true;//如果小于要求子弹个数
}
int main()
{
cin>>n>>k;
for(ll i=1;i<=n;i++)
{
cin>>Hp[i];
}
while(l<=r)//对p的范围进行二分操作
{
mid=(l+r)>>1;
if(check(mid))
{
r=mid-1;
ans=mid;
}
else l=mid+1;
}
printf("%lld",ans);
return 0;
}