记录编号	349001	评测结果	AAAAAAAAAA
题目名称	社长的qwa	最终得分	100
用户昵称	最长上升子序列	是否通过	通过
代码语言	C++	运行时间	0.654 s
提交时间	2016-11-14 18:25:18	内存使用	0.62 MiB

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

typedef long long lnt;
const int up=40000+5;
lnt a[up],minn;int n,k;
lnt qiu(int);

int main()
{
    freopen("qwa.in","r",stdin);
    freopen("qwa.out","w",stdout);

    scanf("%d %d",&n,&k);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    sort(a+1,a+n+1);
    int l=k-k+1,r=k,ne=k;
    while(l<r) minn+=(a[r]-a[l])*((ne-=2)+1),l++,r--;
    for(int i=k;i<=n;i++) minn=min(minn,qiu(i));
        /*if(a[minn]-a[minn-k+1]>a[i]-a[i-k+1]) minn=i;
        else if(a[minn]-a[minn-k+1]==a[i]-a[i-k+1]) minn=(qiu(minn)>qiu(i)?i:minn);*/
    printf("%lld",minn);

    return 0;
}

lnt qiu(int i)
{
    int l=i-k+1,r=i,ne=k;lnt sum=0;
    while(l<r && sum<minn) sum+=(a[r]-a[l])*((ne-=2)+1),l++,r--;
    return sum;
}