CF1651F Tower Defense

本文主要是介绍CF1651F Tower Defense，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

CF1651F Tower Defense

洛谷CF1651F Tower Defense

题目大意

有$n$座防御塔按$1$到$n$的顺序排成一列，每座防御塔都有一个能量上限$c_i$和能量回复速率$r_i$。对于一座塔$i$，每过一秒，它的能量$w_i$就会变成$\min (w_i+r_i,c_i)$，每座塔在初始时满能量。

有$q$个怪物，每个怪物都有两个属性$t_i$和$h_i$，表示这个怪物会在第$t_i$秒出现在第一座塔前。当它到第$j$座塔前时，自己的血量$h_i$会减少$\min (h_i,w_j)$，塔的能量也会减少这个数。当怪物的血量$h_i=0$时怪物停止移动，否则它下一秒会移动到下一座塔。

有些怪物在经过塔$n$后血量仍未减少至$0$，求这样的怪物最终剩下的血量的总和。

注意每座塔是先恢复能量再打怪物。

• $1\le n,q\le 2\times 10^5$
• $1\le c_i,r_i\le 10^9$
• $1\le h_i\le 10^{12}$
• $0\le t_i\le 2\times 10^5$
• $\forall 1\le j<q,t_j<t_{j+1}$

题解

考虑对塔进行分块，当一个怪进入一个块内的塔时，只有两种情况：

• 块内所有塔把怪打了一遍之后怪还有血，这时可以看作块中所有塔内的能量都被清零了
• 怪被块中的一座塔打到血量为$0$，此时这个怪不会再对后面的块产生贡献

我们发现，因为一个怪最多会被打空血一次，所以第二种情况只会出现$O(q)$次。

对于每个块，维护一个推平标记$fl$表示这个块是否被推平，以及$lst$表示这个块上次被操作的时间戳。预处理出每个块被清零后$t$秒这个块的能量总和$p{r}_t$，对于每个怪依次处理每个块：

• 如果这个块没被推平或怪能被块中的一座塔打空血，则暴力遍历一遍这个块，并判断这个怪是否能推平这个块
• 否则，直接把这个怪的血量减去预处理出的值，推平标记不变

我们发现，一开始有$n$个块没被推平，后面每个怪都会使得有最多一个块从被推平状态变为没被推平状态，也就是说第一种情况只会出现$O(n+q)$次。每次$O(\sqrt{n})$暴力修改，均摊下来的时间复杂度为$O((n+q)\sqrt{n})$。

每个怪最多遍历$\sqrt{n}$个块，所以第二种情况的时间复杂度为$O(q\sqrt{n})$。

下面考虑如何对每个块求$p{r}_t$。因为$1\le t_i\le 2\times 10^5$，所以我们只需要求$1\le t\le 2\times 10^5$的$p{r}_t$即可。

设当前块在第$0$时刻清零，当前时刻为$t$，则对于块中的每一座塔$i$，分为三种情况：

• 若$1\le t\le \lfloor \frac{c_i}{r_i}\rfloor$，则从$t-1$到$t$这一单位时间，塔$i$贡献了$r_i$的能量
• 若$t=\lfloor \frac{c_i}{r_i}\rfloor +1$，则从$t-1$到$t$这一单位时间，塔$i$贡献了$c_i\mathrm{mod}{r}_i$的能量
• 若$t\ge \lfloor \frac{c_i}{r_i}\rfloor +2$，则从$t-1$到$t$这一单位时间，塔$i$没有贡献能量

我们考虑维护每一秒的能量增量的差分，做一次前缀和就能得到每一秒的能量增量，再做一次前缀和即可得到$p{r}_t$。

这样每求一块的$p{r}_t$是$O(n)$的，总共有$\sqrt{n}$块，所以预处理的时间复杂度为$O(n\sqrt{n})$。

虽然时间复杂度是$O((n+q)\sqrt{n})$的，但这题的空间复杂度是$O(n\sqrt{n})$的，数组开不下。我们考虑如何降低空间复杂度。

我们可以先把询问离线下来，然后一块一块地做，每块都将每个怪处理一次，这样就只需保留当前块的$p{r}_t$和推平标记，空间复杂度就降为$O(n)$了。

总时间复杂度为$O((n+q)\sqrt{n})$，空间复杂度为$O(n)$。

code

#include<bits/stdc++.h>
using namespace std;
const int N=200000;
int n,q,bl;
long long ans=0,C[N+5],R[N+5],t[N+5],h[N+5],w[N+5],pr[N+5],v[N+5];
int pos(int i){return (i-1)/bl+1;
}
void init(int l,int r){long long wt=0;for(int i=0;i<=N;i++) v[i]=0;for(int i=l;i<=r;i++){wt+=R[i];if(C[i]/R[i]>=N) continue;v[C[i]/R[i]+1]+=C[i]%R[i]-R[i];v[C[i]/R[i]+2]+=-C[i]%R[i];}for(int i=1;i<=N;i++){wt+=v[i];pr[i]=pr[i-1]+wt;}
}
void solve(int l,int r){init(l,r);int fl=0,lst=0;for(int i=1;i<=q;i++){if(!h[i]) continue;if(!fl||fl&&h[i]<=pr[t[i]-t[lst]]){fl=1;for(int j=l;j<=r;j++){w[j]=min(C[j],w[j]+(t[i]-t[lst])*R[j]);if(h[i]>=w[j]){h[i]-=w[j];w[j]=0;}else{w[j]-=h[i];h[i]=0;fl=0;}}}else h[i]-=pr[t[i]-t[lst]];lst=i;}
}
int main()
{
//	freopen("dinosaurs.in","r",stdin);
//	freopen("dinosaurs.out","w",stdout);scanf("%d",&n);bl=sqrt(n);for(int i=1;i<=n;i++){scanf("%lld%lld",&C[i],&R[i]);w[i]=C[i];}scanf("%d",&q);for(int i=1;i<=q;i++){scanf("%lld%lld",&t[i],&h[i]);}for(int i=1;i<=pos(n);i++){solve(i*bl-bl+1,min(i*bl,n));}for(int i=1;i<=q;i++) ans+=h[i];printf("%lld",ans);return 0;
}

这篇关于CF1651F Tower Defense的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---