首页 > 代码库 > HDU 4970 Killing Monsters

HDU 4970 Killing Monsters

2024-07-18 16:48:41   224人阅读

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

具体做法：

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

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

 

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

 

 1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 using namespace std; 5  6 const int maxn = 100005 ; 7  8 long long attack[maxn]; 9 long long sum[maxn];10 11 int main (){12     int n,m,l,r,d,k,x,ans;13     long long h;14     while (~scanf ("%d",&n)&&n){15         memset (attack,0,sizeof attack);16         scanf ("%d",&m);17         while (m--){18             scanf ("%d%d%d",&l,&r,&d);19             attack[l]+=d;20             attack[r+1]-=d;21         }22         long long temp=0;23         for (int i=1;i<=n;i++){24             temp+=attack[i];25             attack[i]=temp;26         }27         temp=0;28         for (int i=n;i>=1;i--){29             temp+=attack[i];30             sum[i]=temp;31         }32         scanf ("%d",&k);33         ans=0;34         while (k--){35             scanf ("%I64d%d",&h,&x);36             if (sum[x]<h)37                 ans++;38         }39         printf ("%d\n",ans);40     }41     return 0;42 }

 


联系
我们