题解：P13416 [COCI 2012/2013 #4] RAZLIKA

lzk9999 · 2025-08-21 23:29:05 · 题解

首先我们先简单理一下思路：

1.排序数组：首先对数组进行排序，这样问题就变成了选择连续的一段数字

2.关键观察：我们需要选择长度为 L = N-K 的连续子数组

3.计算差值：

sum = 子数组最大值 - 最小值 maxn = 子数组内相邻数字的最小差值

4.寻找最优解：遍历所有可能的连续子数组，计算 M+m 的最小值

好了，我们分析完了，直接上AC代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,k;
    cin>>n>>k;
    vector<long long> a(n);   // 动态数组 
    for(int i=0;i<n;i++) cin>>a[i];
    sort(a.begin(),a.end()); // 排序数组
    int s=n-k;  // 剩余数字的数量
    long long maxn2=LONG_LONG_MAX;
    for(int i=0;i<=k;i++){    // 遍历所有可能的连续子数组
        int start=i,end=i+s-1;   //  起始值和结束值 
        long long sum=a[end]-a[start];      // 计算最大差值 M
        long long maxn=LONG_LONG_MAX;        // 计算最小相邻差值 m
        for(int j=start;j<end;j++) {
            long long ans=a[j+1]-a[j];
            if(ans<maxn) maxn=ans;     // 手动更新最小值
        }
        if(sum+maxn<maxn2) maxn2=sum+maxn;
    }
    cout<<maxn2<<endl;
    return 0;
}