Jisoo

这个题目怎么搞：胡搞。

首先运用初中数学知识，把贡献算出来，得到的是

$\sum_{i-1}^{\frac{m}{2}}(m-2 \times (i-1)-1)\times (a_{n-i+1 -} a_i)$

系数是个正在递减的等差数列，并且保证m为偶数。

贪，开始贪，尽可能地选两边的开始伸展，向里面收缩.

这样就处理掉了当k等于1的时候

k为2怎么办，先贪心一波，试图把左边的往右挪或者反过来，把最右边的往左挪。如果不行，就对左边第二个执行此操作，右边同理。
无解是什么情况呢？所有的都相同||$n==m$

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
template<class T>
#define int long long
void read(T &now){
    now=0;
    char c=getchar();
    int f=1;
    while((!isdigit(c))){
        if(c=='-') f=-1;
    //  cout<<isdigit(c)<<" "<<c<<" ";
        c=getchar();
    }
    while(isdigit(c)){
        now=(now<<1)+(now<<3)+c-'0';
        c=getchar();
    }
    now*=f;
}
int a[3000005];
int ans;
int n,m;
int k;
int L,R;
int f;
signed main(){
    read(n);read(m);read(k);
    for(int i=1;i<=n;++i){
        read(a[i]);
    }
    for(int i=2;i<=n;++i){
        if(a[i]!=a[i-1]){f=1;break;}
    }
    sort(a+1,a+n+1);
    for(int i=1;i<=m/2;++i){
        ans+=(m-2*(i-1)-1)*(a[n-i+1]-a[i]);
    }
    if(k==1){
        printf("%lld",ans);
        return 0;
    }else{
        if(f==0||n==m){
            printf("-1");
            return 0;
        }
        for(int i=m/2+1;i<=n-m/2;++i){
            if(a[i]!=a[m/2]){
                L=a[i]-a[m/2];
                break;
            }
            if(i==n-m/2)
            for(int j=m/2-1;j>=1;--j){
                if(a[j]!=a[i]){
                    L=(m-2*j+1)*(a[m/2]-a[j]);
                    break;
                }
            }
        }
        for(int i=n-m/2;i>=m/2+1;i--){
            if(a[i]!=a[n-m/2+1]){
                R=a[n-m/2+1]-a[i];
                break;
            }
            if(i==m/2+1){
                for(int j=m/2+2;j<=n;++j){
                    if(a[j]!=a[n-m/2+1]){
                        R=(m+2*(j-n)-1)*(a[j]-a[n-m/2+1]);
                        break;
                    }
                }
            }
        }
        cout<<max(ans-L,ans-R);
    }
    return 0;
}