2014多校9 1011
http://acm.hdu.edu.cn/showproblem.php?pid=4970
Killing MonstersTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others) Problem Description
Kingdom Rush is a popular TD game, in which you should build some
towers to protect your kingdom from monsters. And now another wave of monsters is coming and you need again to know whether you can get through it. The path of monsters is a straight line, and there A witch helps your enemies and makes Now that Input
The input contains multiple test cases.
The first line of each case is an integer N (0 < N <= 100000), The input is terminated by N = 0. Output
Output one line containing the number of surviving monsters.
Sample Input
5
2 1 3 1 5 5 2 5 1 3 3 1 5 2 7 3 9 1 0 Sample Output
3
Hint
In the sample, three monsters with origin HP 5, 7 and 9 will survive. Source
Recommend
|
题意:塔防,怪走一条直线,可以分成1~n共n格。给出m个塔的攻击范围(Li~Ri),攻击力Di,怪物走过这格会减少Di血量。给出k个怪物的血量、出生格,求有多少个怪物可以走到终点。
题解:差分数列搞。
粗略一看,是区间加减、区间求和,线段树!会超时,怕了。
再一看,是区间加减完再区间求和,而且求和还是有限制的,就求i~n的和。
用差分数列可以轻松区间加减,差分数列就是b[i]=a[i]-a[i-1],区间[i,j]加D就是b[i]=b[i]+d , b[j+1]=b[j+1]-d。
但是怎么求和呢?我们把和写出来观察一下:
an = bn
an-1 + an =2an - bn
an-2 + an-1 + an = 3an - 2bn - bn-1
看起来很好算的样子!
于是这样就能算(其中an就是an ,其中c[i]就是ai加到an的和):
ll one=an,many=an;
for(i=n;i>;i--){
c[i]=many;
one-=b[i];
many+=one;
}
这样就轻松算啦。
我一开始想到差分数列,不过没仔细想怎么求和,然后就去线段树了,逗乐。后来才发现居然这么好求。
全代码:
//#pragma comment(linker, "/STACK:102400000,102400000")
#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<stack>
#include<queue>
using namespace std;
#define ll long long
#define usll unsigned ll
#define mz(array) memset(array, 0, sizeof(array))
#define minf(array) memset(array, 0x3f, sizeof(array))
#define REP(i,n) for(i=0;i<(n);i++)
#define FOR(i,x,n) for(i=(x);i<=(n);i++)
#define RD(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d%d",&x,&y)
#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define WN(x) prllf("%d\n",x);
#define RE freopen("D.in","r",stdin)
#define WE freopen("1biao.out","w",stdout)
#define mp make_pair
#define pb push_back const int maxn=; int n,m,k;
int l[maxn],r[maxn],d[maxn];
int x[maxn];
ll h[maxn];
ll b[maxn];
ll c[maxn];
ll an=; void Update(int L, int R, int x){
b[L]+=x;
b[R+]-=x;
if(R==n)an+=x;
} int main(){
int i;
while(scanf("%d",&n)!=EOF){
if(n==)break;
scanf("%d",&m);
mz(b);mz(c);an=;
REP(i,m) {
scanf("%d%d%d",&l[i],&r[i],&d[i]);
Update(l[i],r[i],d[i]);
}
ll one=an,many=an;
for(i=n;i>;i--){
c[i]=many;
one-=b[i];
many+=one;
}
//for(i=1;i<=n;i++)printf("%I64d\n",c[i]);
int ans=;
//for(i=1;i<=n;i++)printf("(%d,%d),%d\n",i,n,Query(i,n,1,n,1));
scanf("%d",&k);
REP(i,k) {
scanf("%I64d%d",&h[i],&x[i]);
if(c[x[i]]< h[i])ans++;
}
printf("%d\n",ans);
}
return ;
}