自动搬运

查看原文

来自洛谷，原作者为

	Trump__Biden AFO||抚平回忆留下的疤。||谁念西风独自凉 。

搬运于2025-08-24 22:28:09，当前版本为作者最后更新于2022-08-25 11:14:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

传送门

思路：

首先，定义一个结构体：

struct node
{
	long long p,c;
}a[100005];

$p$ 表示该探测器探测到的位置。$c$ 表示电话总数。 将它们输入后调用 cmp 函数，即按 $p$ 进行排序：

bool cmp(node x,node y)
{
	return x.p<y.p;
}

再定义一个数 $s$ 并赋初值为 $0$，然后进行循环。如果第 $i$ 个探测器检测到的数量比它的上一个大，$ans$ 加上多出的数量，将 $s$ 的值更新，最后输出 $ans$。

AC 代码如下：

#include<bits/stdc++.h>
using namespace std;
long long n,m,ans;//开了 long long 不会见祖宗 
struct node
{
	long long p,c;
}a[100005];//结构体 
bool cmp(node x,node y)
{
	return x.p<y.p;
}//排序 
int main()
{
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++)
	  scanf("%lld%lld",&a[i].p,&a[i].c);
	sort(a+1,a+1+n,cmp);//用cmp进行排序 
	int s=0;
	for(int i=1;i<=n;i++)
	{
		if(a[i].c>s)
		  ans+=a[i].c-s;
		s=a[i].c;//更新s的值 
	}
	printf("%lld",ans);
	return 0;//完结散花
}

参考了 @HarunluoON 的思路，加入了自己的想法，如有不足请 dalao 指出。