自动搬运

查看原文

来自洛谷，原作者为

	AW_BCH 迷途.

搬运于2025-08-24 21:17:37，当前版本为作者最后更新于2025-02-23 16:50:21，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题解：B4179 [厦门小学生 C++ 2024] 战线巡逻

题目传送门

更好的阅读体验

题目分析

一道很明显的贪心题。分析一下题意，很容易想到，对于每个需要被巡逻的点，都有两种被士兵巡逻到的情况：

1. 一开始就被士兵直接部署。这种情况下，所需要的体力总和不变。

2. 一开始没有被士兵部署，由离目前最近的被部署的点上的士兵巡逻。这种情况下，所需要的体力总和要加上这两点之间的距离。

分析到这里，就有了一个问题：我们怎么找到离目前的这个点最近的点呢？

答案很明显，可以把所有的点排序，然后依次求出两点之间距离。

实在想不到的看一下题目标签就想到了。

代码实现

• 我们用 num 变量来表示会有几个点没有被士兵直接部署。

• 我们用 cha 数组来表示排序后相邻两个点的距离。

• 我们用 ans 变量来表示答案。

还有一些细节在注释里。

代码：

//洛谷 B4179 [厦门小学生 C++ 2024] 战线巡逻
#include<bits/stdc++.h>
using namespace std;
//#define int long long//
#define endl '\n'
#define emdl '\n'
typedef long long ll;
const int MAXN=1e5+5;
int k,n;
int num,ans;
int a[MAXN];
int cha[MAXN];//a[i] 和 a[i-1] 的差 
//注意：cha[1] 始终为 0
//所以排序时要直接从 cha[2] 开始排 
signed main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>k>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	num=n-k;
	//如果 num<=0 那么直接将士兵部署到点上
	if(num<=0){
		//此时答案为 0 
		cout<<0<<endl;
		return 0;
	}
	sort(a+1,a+1+n);
	for(int i=2;i<=n;i++){
		cha[i]=a[i]-a[i-1]; 
	}
	//直接从 cha[2] 开始排 
	sort(cha+2,cha+n+1);
	for(int i=2;i<=num+1;i++){
		ans+=cha[i];
	}
	cout<<ans<<emdl;
	return 0;
}