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

这道题目的标签是贪心，所以我也用贪心的思路讲解。

这道题目消耗的体力就是各个需要巡逻的点之间的距离，而每多一个哨兵就可以减少其中一段需要消耗的体力，列举三个样例就会发现，一共可以减少

(k-1)

个距离。

代码如下：

CPP

#include<bits/stdc++.h>
using namespace std;
const int maxN=1e5+100;
int a[maxN],s[maxN];
int main(){
	int k,n,ans=0;
	cin>>k>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	} 
	sort(a+1,a+n+1);//记得排序 。 
	for(int i=1;i<n;i++){
		s[i]=a[i+1]-a[i];//计算每个距离 。 
	}
	sort(s+1,s+n,greater<int>());//给每个距离做降序排序 。 
	for(int i=k;i<n;i++){
		ans+=s[i];//减少 (k-1) 个最大的距离，从 k 开始遍历相加。 
	}
	cout<<ans;
	return 0;
}

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

文章操作

相关推荐

评论

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