湖南大学2025暑期培训练习赛二Problem A: Tower Defense-EW帮帮网

Problem A: Tower Defense

Problem Statement

There are cells labeled from 1 to N arranged in sequence. Cell 1 contains a base, and cell N contains a monster with health H. There are M soldiers deployed near the cells. The attack range of soldier i is from cell $L_i`$ to $R_i`$ (i.e., cells $L_i, L_i+1, ..., R_i`$ ).

Each turn, both the monster and the soldiers perform the following actions in order (first the monster, then the soldiers):

Monster: If the monster’s health is 1 or more and it is not in cell 1, it moves one cell closer to the base (i.e., it moves to the cell with a number smaller).
Soldiers: Any soldier whose attack range includes the cell where the monster is currently located attacks the monster and reduces its health by 1.

If the monster’s health drops to 0 or below before it reaches cell 1, the monster dies in that cell, the defense is successful, and the game ends. If the monster reaches cell 1 without its health dropping to 0 or below, the defense fails and the game ends.

Determine whether the defense will succeed, and if so, find the number of the cell where the monster will die.

Input

The input consists of a single test case of the following format.

M N H
L1 R1
L2 R2
...
LM RM

The first line contains three integers M, N, and H, representing the number of soldiers, the number of cells, and the monster’s health, respectively. M is between 1 and 100 (both inclusive). N is between 2 and 1000 (both inclusive). H is between 1 and 1000 (both inclusive).
The next M lines each contain two integers $L_i`$ and $R_i`$ , which represent the attack range interval of the i-th soldier. Both $L_i`$ and $R_i`$ are between 1 and N (both inclusive). It is guaranteed that $L_i`$ is less than or equal to $R_i`$ .

Output

Output a single integer, the number of the cell where the monster will die if the defense is successful; otherwise, output -1.

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

-1

根据题目描述，我们需要模拟怪物从位置 ( M ) 移动到位置 ( 0 ) 的过程，并在每个位置（移动后）受到该位置上所有士兵的攻击。如果怪物在到达位置 ( 0 ) 前血量降至 ( 0 ) 或以下，则输出死亡位置；否则输出 (-1)。

解题思路

差分数组处理士兵覆盖范围：使用差分数组记录每个位置被士兵覆盖的次数。对于每个士兵的区间 ([L_i, R_i])，在 ( L_i ) 处加 1，在 ( R_i + 1 ) 处减 1。
前缀和计算每个位置的攻击次数：通过差分数组的前缀和，计算每个位置 ( i )（从 1 到 ( M )) 被士兵覆盖的次数（即攻击次数）。
模拟怪物移动与攻击：怪物从位置 ( M ) 开始，但首次攻击发生在位置 ( M-1 )（因为怪物先移动再攻击）。从 ( M ) 遍历到 1：
- 在位置 ( i )，怪物受到该位置攻击次数的伤害（血量减少）。
- 若血量 ( \leq 0 )，则输出当前位置 ( i ) 并结束。
处理防御失败：若遍历完所有位置（到位置 1）后血量仍 > 0，则怪物到达位置 0，输出 (-1)。

代码说明

差分数组处理：通过 sum[l]++ 和 sum[r+1]-- 标记士兵覆盖的区间。
前缀和计算：循环计算前缀和，sum[i] 表示位置 ( i ) 被士兵覆盖的次数。
怪物移动模拟：从 ( M ) 到 1 逆序遍历，模拟怪物移动过程。在位置 ( i ) 减去攻击次数，若血量 ( \leq 0 ) 则输出位置并结束。
防御失败处理：若遍历结束血量仍 > 0，输出 (-1)。

该算法时间复杂度为 ( O(N + M) )，其中 ( N ) 为士兵数，( M ) 为位置数，满足题目约束。

代码实现

#include<bits/stdc++.h>
#define ll long long
#define samplepassediscorrect for(;;)
#define ull unsigned long long
#define jiasu ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define lowbit(x) (x&(-x))
#define N 1000005
using namespace std;
ll n,m,h,sum[N],l,r;
int main(){
jiasu;
cin>>n>>m>>h;
while(n--){
	cin>>l>>r;
	sum[l]++,sum[r+1]--;
}
for(int i=1;i<=m;i++)
	sum[i]+=sum[i-1];
for(int i=m;i>=1;i--){
	h-=sum[i];
	if(h<=0){
		cout<<i;
		return 0;
	}
}
cout<<-1;
	return 0;
}

湖南大学2025暑期培训练习赛二Problem A: Tower Defense