首页 > 代码库 > HDU 4970

HDU 4970

2024-07-18 15:57:32   214人阅读

http://acm.hdu.edu.cn/showproblem.php?pid=4970

比赛的时候线段树水过的，比赛后线段树一直T，看了下正解真的是智商压制

题意：走直线，长度1-N，还有一些人，起点任意，每个人有血量，m个塔，每个塔有攻击范围和伤害，在一个点只会受到塔一次攻击，走到N存活，问存活个数

用一个数组ak记录塔的起点和终点情况，每个塔攻击起点加塔的伤害值，终点+1减伤害值

再用一个新数组sum，从前到后扫一遍可以知道每个点出发时的伤害(sum[i]=sum[i-1]+ak[i])，再从后往前扫一遍可以知道每个点到N的伤害(sum[i]+=sum[i+1])

这样得到的sum[i]就表示从i-N会损失的血量

#include <iostream>#include <cstdio>#include <cstring>using namespace std ; typedef __int64 ll ;ll ak[100005],sum[100005] ;int main(){    int n ;    while(~scanf("%d",&n),n)    {        int m,k ;        scanf("%d",&m) ;        memset(ak,0,sizeof(ak)) ;        memset(sum,0,sizeof(sum)) ;        while(m--)        {            int L,R,D ;            scanf("%d%d%d",&L,&R,&D) ;            ak[L]+=(ll)D ;            ak[R+1]-=(ll)D ;        }        for(int i=1 ;i<=n ;i++)        {            sum[i]=sum[i-1]+ak[i] ;        }        for(int i=n-1 ;i>0 ;i--)           {               sum[i]+=sum[i+1] ;           }        scanf("%d",&k) ;        int ans=0 ;        while(k--)        {            int x ;            ll h ;            scanf("%I64d%d",&h,&x) ;            if(sum[x]<h)ans++ ;        }        printf("%d\n",ans) ;    }    return 0 ;}
View Code

 


联系
我们