Untitled

mail@pastecode.io avatar
unknown
c_cpp
2 years ago
1.4 kB
14
Indexable
Never
#include<bits/stdc++.h>
using namespace std;

struct PAIR
{
    long long a,b,c;
};

bool compare(PAIR fi,PAIR se)
{
    return fi.c<se.c;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    long long n,k;
    cin>>n>>k;
    long long a[n+1];
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    long long f[n+1][n+1];
    for(int i=1;i<=n;i++)
    {
        for(int j=i;j<=n;j++)
        {
            f[i][j]=abs(a[i]-a[j]);
        }
    }
    vector<PAIR>t;
    long long index=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=i;j<=n;j++)
        {
            if(i!=j)
            {
                t.push_back(PAIR());
                t[index].a=i;
                t[index].b=j;
                t[index].c=f[i][j];
                index++;
            }
        }
    }
    sort(t.begin(),t.end(),compare);
    long long res=1e9;
    for(int i=0;i<t.size();i++)
    {
        long long temp=t[i].c,l=1;
        map<long long,long long>cnt;
        cnt[t[i].b]++;
        cnt[t[i].a]++;
        for(int j=0;j<t.size();j++)
        {
            if(l==k) break;
            if(cnt[t[j].a]==0&&cnt[t[j].b]==0)
            {
                temp+=t[j].c;
                cnt[t[j].a]++;
                cnt[t[j].b]++;
                l++;
            }
        }
        res=min(res,temp);
    }
    cout<<res;
    return 0;
}