小鑫杀怪兽

比眉伴天荒 2022-08-18 02:29 76阅读 0赞

## 小鑫杀怪兽 ##

####  ####

##### Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^\_^ #####

## 题目描述 ##

塔防游戏是一类很出名的游戏，在游戏里，你需要建造一些防御塔来攻击怪兽从而保卫小鑫国王。现在又有一波怪兽来袭了，你需要知道小鑫国王能否顶住怪兽的攻击。

怪兽所走的路是一条直线，这条直线上有N个格子（连续编号从1到N）。在怪兽敌人赶来之前，你需要建造M个防御塔。每个防御塔的攻击范围是\[L, R\]，意味着这个防御塔可以攻击从L到R之间所有的敌人。当某个怪兽待在第i个位置时，每一个能攻击到第i个位置的防御塔都会对这个怪兽进行一次攻击，怪兽在进行下一次移动之前不会再受到同一个防御塔的攻击。举个例子，一个防御塔的攻击范围是\[1, 3\]，一个怪兽会在第1个格子、第2个格子、第3个格子分别受到1次攻击。

一个邪恶的女巫会帮助所有的怪物安置初始位置（第i个怪兽出现在格子Xi）。所有的怪兽都沿直线行动（沿着从1到N的方向）。

现在你知道每个怪兽的血量Hi 以及每个防御塔的伤害值Di ，（一次攻击会对怪兽造成Di点伤害，怪兽的血量会下降Di）。如果一个怪兽的血量Hi降低到0或者0以下，这个怪兽就会被打死然后消失。

你的任务是计算最经过所有的防御塔攻击，会留下多少的怪兽。

## 输入 ##

输入包含多组。

每组的第一行是一个整数N (0 < N <= 100000)，代表路上一共有N个格子。第二行是一个整数M (0 < M <= 100000)，代表小鑫拥有的防御塔的数量。接下来M行，每行包含三个整数Li, Ri, Di (1 <= Li <= Ri <= N, 0 < Di <= 1000)，代表防御塔的攻击范围\[L, R\]以及防御塔的伤害值。接下来一个整数K (0 < K <= 100000)，代表怪兽的数量。接下来K行，每行有两个整数Hi 和 Xi (0 < Hi <= 10^18, 1 <= Xi <= N)，代表怪兽的血量以及怪兽的起始位置。

当N = 0时输入结束。

## 输出 ##

输入一个整数，代表最后存活的怪兽的数量。

## 示例输入 ##

5
    2
    1 3 1
    5 5 2
    5
    1 3
    3 1
    5 2
    7 3
    9 1
    0

## 示例输出 ##

## 提示 ##

提示：

在样例中，初始血量为5、7和9的三个怪兽最后还存活着。

## 来源 ##

GLSilence

## 示例程序 ##

#include<stdio.h>  
    #include<string.h>  
    long long a[100000];  
    int main()  
    {  
    long long i,j,n,m,k,t,x,y,z;  
    while(scanf("%lld",&n)&&n)  
    {  
    memset(a,0,sizeof(a));  
    scanf("%lld",&m);  
    for(i=0;i<m;i++)  
    {  
    scanf("%lld %lld %lld",&x,&y,&z);  
    a[y+1]-=z;  
    a[x]+=z;  
    }  
    for(i=1;i<=n;i++)  
    a[i]+=a[i-1];  
    for(i=n-1;i>0;i--)  
    a[i]+=a[i+1];  
    scanf("%lld",&t);  
    k=t;  
    while(t--)  
    {  
    scanf("%lld %lld",&z,&x);  
    if(a[x]>=z)  
    k--;  
    //printf("%d\n",a[x]);  
    }  
    printf("%d\n",k);  
    }  
    }