HDU 4970 Killing Monsters

开始以为是线段树,算了一下复杂度也觉得能过。。。但是这题貌似卡了线段树。。。

具体做法:

  对每一个塔,记录attack[l]+=d,attack[r+1]-=d;这样对于每个block,受到的伤害就是前缀和attack[1]+attack[2]+...+attack[i];

  从后往前遍历,计算从当前点到结束受到的总的伤害;

ps:貌似很多人都是用树状数组写的。。。写完还是不太懂和树状数组有什么关系。。。orz

 #include <iostream>
#include <cstring>
#include <cstdio>
using namespace std; const int maxn = ; long long attack[maxn];
long long sum[maxn]; int main (){
int n,m,l,r,d,k,x,ans;
long long h;
while (~scanf ("%d",&n)&&n){
memset (attack,,sizeof attack);
scanf ("%d",&m);
while (m--){
scanf ("%d%d%d",&l,&r,&d);
attack[l]+=d;
attack[r+]-=d;
}
long long temp=;
for (int i=;i<=n;i++){
temp+=attack[i];
attack[i]=temp;
}
temp=;
for (int i=n;i>=;i--){
temp+=attack[i];
sum[i]=temp;
}
scanf ("%d",&k);
ans=;
while (k--){
scanf ("%I64d%d",&h,&x);
if (sum[x]<h)
ans++;
}
printf ("%d\n",ans);
}
return ;
}
上一篇:HTML5夜空烟花绽放动画效果


下一篇:纯CSS实现表单验证