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

· · 题解

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

题目传送门

更好的阅读体验

题目分析

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

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

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

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

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

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

代码实现

还有一些细节在注释里。

代码：

//洛谷 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;
}