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

xiao_young · 2025-02-24 21:24:44 · 题解

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

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

代码如下：

#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;
}