首页 > 代码库 > hdu 4970 killing monster 代代相传刷qq 不用线段树啦~

hdu 4970 killing monster 代代相传刷qq 不用线段树啦~

2024-07-18 15:31:48   225人阅读

【题意】塔防游戏，一条n长的路上，有m个炮台，可以覆盖[li,ri]范围，威力ci，即每一秒，炮塔可以对范围 内的怪物可以造成ci点伤害。只有有q只怪物，每只怪物有hi点血，出现位置为xi；当怪物血量减少到0或以下时消失，怪物一直朝n位置前进。问有几只怪物可以离开这条路。

【题解】用线段树可以做，不过还好我们有代代相传的刷qq 算法 ，让解法变得简单的多~    ^_^

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6  7 using namespace std; 8 __int64 num[100005]; 9 10 struct node{__int64 hp,x;}m[100005];11 12 int cmp(node a,node b)13 {14     return a.x<b.x;15 }16 17 int main()18 {19     int n,k,a,b,d;20     while(~scanf("%d",&n),n)21     {22         scanf("%d",&k);23         memset(num,0,sizeof(num));24         while(k--)25         {26             scanf("%d%d%d",&a,&b,&d);27             num[a]+=d;28             num[b+1]-=d;29         }30         __int64 sum=0;31         for(int i=0;i<=n;i++)32         {33             sum+=num[i];34             num[i]=sum;35         }36         //num[i]:每个点i的攻击力度37         scanf("%d",&k);38         for(int i=0;i<k;i++)39             scanf("%I64d%I64d",&m[i].hp,&m[i].x);40         sort(m,m+k,cmp);41         sum=0;42         int ans=0,j=k-1;43         for(int i=n;i>=0;i--)44         {45             sum+=num[i];          // sum：从点n到点i 怪物会受到的总攻击力度46             while(i==m[j].x)       // 可能有好几个怪物从点i冒出来47             {48                 if(m[j].hp>sum)49                    ans++;50                 j--;51                 if(j<0)52                     break;53             }54             if(j<0)55                 break;56         }57         printf("%d\n",ans);58     }59     return 0;60 }

 


联系
我们