首页 > 代码库 > hdu 4970 Killing Monsters (思维 暴力)

hdu 4970 Killing Monsters (思维 暴力)

题目链接

题意:

有n座塔,每座塔的攻击范围为[l,r],攻击力为d,有k个怪兽从这些塔前面经过,第i只怪兽初始的生命力为hp,出现的位置为x,终点为第n个格子。问最后有多少只怪兽还活着。

分析:

这个题刚开始是想用线段树,但是这个题会超时,线段树是O(nlogn)的复杂度,应该是卡的输入输出,

所以看别人的博客有人用 快速读入的方法用线段树 险过了,就是把每一个当作字符来输入,然后处理成数字。

但是正解是O(n)的处理,即把l, r,  d, 用数组a[l] += d;  a[r+1] = -d; 然后从前向后扫一遍就 能计算出每一个格子的伤害,

把a从后向前扫一遍就能计算出 现在格子到最后一个格子的伤害。

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

 

hdu 4970 Killing Monsters (思维 暴力)