区间整数遍历问题,子序列的遍历怎么使用C语言算法计算实现?

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 are N blocks on it (numbered from 1 to N continuously). Before enemies come, you have M towers built. Each tower has an attack range [L, R], meaning that it can attack all enemies in every block i, where L<=i<=R. Once a monster steps into block i, every tower whose attack range include block i will attack the monster once and only once. For example, a tower with attack range [1, 3] will attack a monster three times if the monster is alive, one in block 1, another in block 2 and the last in block 3.

A witch helps your enemies and makes every monster has its own place of appearance (the ith monster appears at block Xi). All monsters go straightly to block N.

Now that you know each monster has HP Hi and each tower has a value of attack Di, one attack will cause Di damage (decrease HP by Di). If the HP of a monster is decreased to 0 or below 0, it will die and disappear.
Your task is to calculate the number of monsters surviving from your towers so as to make a plan B.

Input
The input contains multiple test cases.

The first line of each case is an integer N (0 < N <= 100000), the number of blocks in the path. The second line is an integer M (0 < M <= 100000), the number of towers you have. The next M lines each contain three numbers, Li, Ri, Di (1 <= Li <= Ri <= N, 0 < Di <= 1000), indicating the attack range [L, R] and the value of attack D of the ith tower. The next line is an integer K (0 < K <= 100000), the number of coming monsters. The following K lines each contain two integers Hi and Xi (0 < Hi <= 10^18, 1 <= Xi <= N) indicating the ith monster’s live point and the number of the block where the ith monster appears.

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

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问

相似问题

2
一个C语言算法题目,帮忙给个思路
2
C++语言编程 最大子段和
4
C++语言编程 运用贪心算法的方法
13
c语言编译的最大子序列求和问题
2
一个C语言算法实际的问题,怎么实现
2
一个多项式,求其前N项和的算法的问题,用C语言
1
关于如何计算机IP地址的判断判定算法C语言
2
C语言写一算法,对输入的表达式中括号匹配情况检查。匹配的括号需要成对出现,且不嵌套。
1
var html="<input >"怎么拿到input的值然后遍历这个值 这个值是个整数
1
C语言判断,是否能找到一个k 的区间,里面的 k 个数字排完序后是连续的
1
输入一个3行4列的整数矩阵,计算并输出对角线上的元素之和
2
找连续数,用C语言编程,有几个这样的 k 的区间。
1
如何使用C语言实现逆波兰运算(加减乘除)求值?
2
给一个整数x将该数插入到序列中,并使新的序列仍然有序,如何C语言
2
整数的拆分和求和,如何使用动规来实现,动归解决数组问题,C语言
1
大整数的连续运算步骤的问题,采用C语言,计算每个序列都要输出
3
C语言实现,给定一段连续的整数,求出他们中所有偶数的平方和以及所有奇数的立方和
0
超大整数的指数级表示的问题,这个使用C语言程序设计的表示
0
整数线性表排序+反转的一个算法,采用C语言如何进行求解答?
1
C程序的实现,给你一个整数区间[a,b],请你求出该区间的x使g(x)最大。