P15743题解

whatareyoudoing

2026-03-19 19:40:17

发布于：福建

7阅读

0回复

0点赞

P15743题解

作者：what_are_you_doing(洛谷Uid:1908713)

未经允许，禁止发布在任何平台。

Apple_pieYES (洛谷Uid:1412516) 可以使用

此图为证

本题使用到了两个算法：

差分和前缀和

这两个算法可以说是一对兄弟，十分相似，也经常用到，我先讲前缀和吧。

前缀和：

有一个数组 $sum = \{5,7,2,9,3\}$ ，我们要求出 $sum[2] \backsim sum[4]$ 的和，我们可以这样写：

cpp

#include<bits/stdc++.h>
using namespace std;
int sum[5]={5,7,2,9,3};
int main(){
	int ans=0;
	for(int i=2;i<=4;i++) ans+=sum[i];
	printf("%d",ans);
	return 0;
}

这样子写虽然方便，但是如果要执行 $10^5$ 次求和、 $10^6$ 次求和，甚至是 $10^9$ 次求和，弊端这不就出来了吗 $？$ 为了我们的代码运行时间更加的快，我们可以使用前缀和。

使用前缀和要定义一个数组，这个数组我们把他叫作 " $ans$ "， $ans[i]$ 表示 $sum[0] \backsim sum[i]$ 的和，即

$\begin{cases} ans[0] = sum[0] \\ ans[i] = sum[i]+ans[i-1]\\ \end{cases}$

这时候，有的同学就要问了：“前缀和有什么用呢，与求和有什么关系吗？”

问得好！奖励一朵小红花。

回到我们最开始的问题，我们可以把求 $sum[2] \backsim sum[4]$ 的和的问题转化一下，可以变成求 $(sum[0] \backsim sum[4])-(sum[0] \backsim sum[1])$ 的值，简化了以后，也就是 $sum[2]+sum[3]+sum[4]$ 的和。

而我们已经求出了 $sum[0] \backsim sum[4]$ 和 $sum[0] \backsim sum[1]$ 的值。分别储存在了 $ans[1]$ 和 $ans[4]$ 里了，直接访问就可以了。

于是，我们可以写出如下代码：

cpp

#include<bits/stdc++.h>
using namespace std;
int ans[5];
int sum[5]={5,7,2,9,3};
int main(){
	memset(ans,0,sizeof(ans));
	ans[0]=sum[0];
	for(int i=1;i<=4;i++) ans[i]=ans[i-1]+sum[i];
	printf("%d",ans[4]-ans[1]);
	return 0;
}

这时，有同学又要问了：“如果题目给我们一个前缀和数组，让我们求原数组，我们要怎么办呢？”

真棒！再奖励一朵小红花。

这时候，就到了差分出场了。

差分：

差分是前缀和的逆运算，前缀和是加，而差分是减，比如这个前缀和数组 $sum=\{5,12,14,23,26\}$

使用查分前也要定义一个数组，这个数组我们把他叫作 " $ans$ "， $ans[i]$ 表示数组原来的值，即

$\begin{cases} ans[0] = sum[0] \\ ans[i] = sum[i]-sum[i-1]\\ \end{cases}$

把我们之前的代码改一下，我们可以写出如下代码：

cpp

#include<bits/stdc++.h>
using namespace std;
int ans[5];
int sum[5]={5,12,14,23,26};
int main(){
	memset(ans,0,sizeof(ans));
	ans[0]=sum[0];
	for(int i=1;i<=4;i++) ans[i]=sum[i]-sum[i-1];
	for(int i=0;i<=4;i++) printf("%d ",ans[i]);
	return 0;
}

输出：

5 7 2 9 3

与前缀和不同的是：前缀和可以在原数组上做出更改，但是差分不可以在原数组上更改，运行下面的两个代码就可以知道了。

代码如下(cpp)

前缀和代码

#include<bits/stdc++.h>
using namespace std;
int sum[5]={5,7,2,9,3};
int main(){
	for(int i=1;i<=4;i++) sum[i]=sum[i-1]+sum[i];
	for(int i=0;i<=4;i++) printf("%d ",sum[i]);
	return 0;

输出：

5 12 14 23 26

差分代码

#include<bits/stdc++.h>
using namespace std;
int sum[5]={5,12,14,23,26};
int main(){
	for(int i=1;i<=4;i++) sum[i]=sum[i]-sum[i-1];
	for(int i=0;i<=4;i++) printf("%d ",sum[i]);
	return 0;
}

输出：

5 7 7 16 10

而正确的输出是：

5 7 2 9 3

所以，我们在使用差分时要注意哦！！！

这时有同学提问了：“差分又有什么用呢？”

你真是太棒了！奖励一朵小黄花！！！

我们新建一个数组 $ans[5]$ ，把 $ans$ 清 $0$ ，然后我们把 $ans[0]$ 加 $1$ 。

这个时候，数组 $ans$ 为：

1,0,0,0,0

而这个数组的前缀和数组为：

1,1,1,1,1

我们只用把 $ans[i]$ 加 $1$ , $ans[i]$ 后面的所有值也都自动加 $1$ 了。

所以：
把 $ans[i]$ 加 $2$ , $ans[i]$ 后面的所有值也都自动加 $2$ 了;
把 $ans[i]$ 减 $1$ , $ans[i]$ 后面的所有值也都自动减 $1$ 了。

我们再把 $ans[3]$ 减去 $1$ ，这时候，前缀和数组变为：

1,1,0,0,0

利用这个性质，我们就可以解决这道题了。

题目传送门

因为怪物会经过每一个格子，所以我们先计算出经过每一个格子，怪物会受到的伤害总数。

因为怪物在士兵的攻击范围内，都会受到 $1$ 点伤害，所以我们用一个初始值全部为零的数组 $ans$ 存伤害，每次输入两个数（ $L_i$ 和 $R_i$ ）时，我们将 $ans[L_i]+1$ ， $ans[R_i+1]-1$ ，在输入完成后，我们只用算一下前缀和，就可以得出怪物经过每一个格子所受到的伤害了。

~~剩下的代码，我相信你们会写。~~

对了，我要提醒一句：

十年ＯＩ一场空，不开long long 见祖宗

话不多说，上代码：

#include<bits/stdc++.h>
using namespace std;
long long sum[2000005];
int main(){
    long long n,m,h;
    scanf("%lld%lld%lld",&n,&m,&h);
    long long l,r;
    for(int i=1;i<=n;i++){
        scanf("%lld%lld",&l,&r);
        sum[l]+=1;
        sum[r+1]-=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){
            printf("%lld",i);
            return 0;
        }
    }
    printf("-1");
    return 0;
}