Angry Children 2

                            Solution in C :

In c++ :





#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 100005;
long long a[N], sum[N];
long long s(int a, int b) { return sum[b] - (a ? sum[a - 1] : 0LL); }

int main()
{
    //freopen("test.in", "r", stdin);
    int n, k;
    scanf("%i %i", &n, &k);
    for(int i = 0; i < n; i++)
        scanf("%lld", &a[i]);
    sort(a, a + n);

    sum[0] = a[0];
    for(int i = 1; i < n; i++)
        sum[i] = sum[i - 1] + a[i];

    long long curr = 0;
    for(int i = 0; i < k; i++)
        curr += (long long)(2 * i + 1) * a[i];

    long long res = curr;
    for(int i = 0; i + k - 1 < n; i++)
    {
        res = min(res, curr - k * s(i, i + k - 1));
        curr -= a[i] + 2LL * s(i + 1, i + k - 1);
        curr += (long long)(2 * k - 1) * a[i + k];
    }
    printf("%lld\n", res);

    return 0;
}








In Java :





import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    static long curTime;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), k = in.nextInt();
        long[] x = new long[n];
        for(int i = 0; i < n; i++) x[i] = in.nextInt();
        Arrays.sort(x);
        curTime = System.currentTimeMillis();
        System.out.println(f(n, k, x));
    }
    
    private static long f(int n, int k, long[] x){
        long t = unFair(k, x), min = t, s = 0;
        //long s = sum(1, k-1, x);
        for(int i = 1; i < k; i++) s += x[i];
        
        for(int i = 1; i + k-1 < x.length; i++){
            //System.out.println(t);
            t += (k-1)*(x[i-1] + x[i+k-1]);
            t -= 2*s;
            if(t < min) min = t;
            s += x[i+k-1] -x[i];
        }
        return min;
    }
    
    private static long unFair(int k, long[] x){
        long s = 0;
        for(int i = 0; i < k; i++){
            s += x[i] *(2*i-k+1);
        }
        return s;
    }
    
    private static long sum(int i, int j, long[] x){
        long s = 0;
        for(int k = i; k <= j; k++) s += x[k];
        return s;
    }
    
    /*private static long aSum(int i, int j, long[] x){
        if(i == j) return x[i];
        return x[j] - aSum(i, j-1, x);
    }*/
}








 In C :





#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

long long int min(long long int a,long long int b){
    if(a<b)
        return a;
    return b;
}

int cmpr(const void * a,const void *b){
    return (*(long long int *)a)-(*(long long int *)b);
}

int main(){
    long long int n,k,i=0,j;
    scanf("%lld %lld",&n,&k);
    long long int a[n];
    while (i<n) {
        scanf("%lld",&a[i]);
        i++;
    }
    qsort(a, n, sizeof(long long int), cmpr);
    i=0;
    j=1-k;
    long long int sum=0,sum1=0;
    while(i<k){
        sum+=a[i]*j;
        sum1+=a[i];
        j+=2;
        i++;
    }
    i=0;
    j=k;
    long long int ans=sum;
    while (j<n) {
        sum1-=a[i];
        sum=sum-(2*sum1)-((1-k)*a[i])+(k-1)*a[j];
        sum1+=a[j];
        ans=min(ans,sum);
        i++;
        j++;
    }
    printf("%lld\n",ans);
    return 0;
}








In Python3 :





n = int(input())
k = int(input())
a = []
for i in range(n):
    a.append(int(input()))
a.sort()
ps = [0]
for i in range(n):
    ps.append(ps[-1] + a[i])
cur = 0
for i in range(k):
    cur += i * a[i] - ps[i]
ans = cur
for i in range(1, n - k + 1):
    cur -= ps[i + k - 1] - ps[i - 1] - k * a[i - 1]
    cur += k * a[i + k - 1] - ps[i + k] + ps[i]
    ans = min(ans, cur)
print(ans)