本文共 2767 字,大约阅读时间需要 9 分钟。
题目描述
输入格式
第二行,n个正整数,第i个正整数表示从左至右数第i只怪物的血量mi。
输出格式
样例输入
3 1
1 4 5
样例输出
6
注释
对于100%的数据,n<=500000,k<=500000,1<=mi<=10^10
一看到这个题就想到了首先肯定打最右面的 打死一个向前走再打最后没死的。。。丧心病狂
然后伤害 就想到了二分
二分很简单 但是验证不简单
由于伤害向左溅射
一开始枚举每一个打的 然后将伤害向左溅射一次 时间复杂度约 N^2 * log N
然后只能过3个点
看题解上说的O(n)验证很厉害啊
节省时间就直接抄过来吧。。。
容易注意到随着p的增大,所需要的子弹数单调递减。于是我们便会想到二分答案,但这并不是难点,本题的难点在于:对于一个二分出的p,如何快速计算出它所需要的子弹数?
由于本题中子弹的溅射伤害只是向左,故很容易想到子弹应从右打起,打到怪物被消灭为止。但如果朴素计算溅射伤害,复杂度可能高达O(n^2),无法通过本题。所以我们需要一个更优的计算方法。
我们设对于二分出的p,射到从左到右第s个怪物身上的子弹数为kk[s]。对于p-(i-j)*(i-j)我们将它拆开,变成-j^2+2ij-i^2+p。对于第j个怪,它受到的溅射伤害应为-(kk[j+1]+...+kk[n])*j^2+2*(kk[j+1]*(j+1)+...+kk[n]*n)*j-(kk[j+1]*(j+1)^2+...+kk[n]*n^2)+(kk[j+1]+...+kk[n])*p。
这其实是把溅射伤害的值表示为一个二次函数。而二次函数每一项的系数都是可累加的,溅射伤害可以随着循环算出。而当p-(i-j)*(i-j)<0时,我们便需要把对应的i从系数中减去。每一位至多只会被减去一次,故总复杂度仍不变,对于一个二分出的p,计算出它所需要的子弹数的时间复杂度仍为O(n)
#include#include #include #include using namespace std;long long s[500011];int use[500011];int m,n,a,b,c;long long l,r,mid,ans;long long lim;long long life;long long T1,T2,T3,used;inline bool ok(){ long long a; memset(use,0,sizeof(use)); used=0;T1=0,T2=0,T3=0; for(a=m;a>=1;a--) { if(use[a+1]) { T1+=use[a+1]; T2+=use[a+1]*(a+1); T3+=use[a+1]*(a+1)*(a+1); } if(a+lim<=m&&use[a+lim]) { T1-=use[a+lim]; T2-=use[a+lim]*(a+lim); T3-=use[a+lim]*(a+lim)*(a+lim); } life=mid*T1-a*a*T1+2*a*T2-T3; if(s[a]>=life) { use[a]=(s[a]-life)/mid+1; used=used+use[a]; } if(used>n)return false; } return true;}int main(){ scanf("%d%d",&m,&n); for(a=1;a<=m;a++) { scanf("%d",&s[a]); r+=s[a]; } l=s[m]/n; r=r/n+1; while(l<=r) { mid=(l+r)>>1; lim=(long long)sqrt(mid)+1; if(ok()) { ans=mid; r=mid-1; } else l=mid+1; } cout< <
一开始写的渣N^2的验证
bool ok(){ int a,b; long long dec; memset(hurt,0,sizeof(hurt)); memset(use,0,sizeof(use)); int used=0; for(a=m;a>=1;a--) { if(s[a]>=hurt[a])use[a]=(s[a]-hurt[a])/mid+1; used=used+use[a]; if(used>n)return false; for(b=a-1;b>=1;b--) { dec=mid-d(a-b); if(dec<=0)break; hurt[b]=hurt[b]+dec*use[a]; } } return true;}
转载地址:https://blog.csdn.net/li412302070/article/details/13613467 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!