首页 > 代码库 > hdu 4970 Killing Monsters

hdu 4970 Killing Monsters

长度为n的直线上有几个防御塔,每个防御塔都有攻击范围为[L,R],然后给出几个怪物的血量和出现位置,问能从出现位置走到末尾的有几个。

对于每次输入的防御塔的L,R和他的攻击力d,a[L]+=d,a[R+1]-=d。然后从1到n累加一遍计算出每个位置的实际伤害。最后从末尾累加到开始计算后缀和。

#include <cstdio>#include <cstring>#include <algorithm>using namespace std;#define maxn 100100typedef long long ll;ll a[maxn];int main(){    int n,m;    while(scanf("%d",&n),n)    {        scanf("%d",&m);        int i,j,x,y,z;        memset(a,0,sizeof(a));        for(i=1;i<=m;i++)        {            scanf("%d%d%d",&x,&y,&z);            a[x]+=z;            a[y+1]-=z;        }        for(i=2;i<=n;i++) a[i]+=a[i-1];        for(i=n-1;i>=1;i--) a[i]+=a[i+1];        int k;        scanf("%d",&k);        ll h;        int sum=0;        while(k--)        {            scanf("%I64d%d",&h,&x);            if(a[x]<h) sum++;        }        printf("%d\n",sum);    }    return 0;}

 

hdu 4970 Killing Monsters