Submission #74943227

---

Source Code Expand

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        long K = Long.parseLong(st.nextToken());
        
        long[] D = new long[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) D[i] = Long.parseLong(st.nextToken());
        
        Arrays.sort(D);
        
        // prefix[i] = D[0] + D[1] + ... + D[i-1]
        long[] prefix = new long[N + 1];
        for (int i = 0; i < N; i++) prefix[i+1] = prefix[i] + D[i];
        
        // For window [s, s+K-1]:
        // cost for left outliers (Di < s): s * count - sum
        // cost for right outliers (Di > e): sum - e * count
        // We try s = D[i] and s = D[i] - K + 1 for each i
        
        long ans = Long.MAX_VALUE;
        long e_val;
        
        // candidates for s
        Set<Long> candidates = new HashSet<>();
        for (long d : D) {
            candidates.add(d);
            candidates.add(d - K + 1);
        }
        
        for (long s : candidates) {
            e_val = s + K - 1;
            
            // left boundary: first index where D[i] >= s
            int lIdx = lowerBound(D, s);
            // right boundary: first index where D[i] > e
            int rIdx = lowerBound(D, e_val + 1);
            
            // left outliers: indices 0..lIdx-1, cost = s*lIdx - prefix[lIdx]
            long cost = s * lIdx - prefix[lIdx];
            
            // right outliers: indices rIdx..N-1, cost = (prefix[N]-prefix[rIdx]) - e*(N-rIdx)
            cost += (prefix[N] - prefix[rIdx]) - e_val * (N - rIdx);
            
            ans = Math.min(ans, cost);
        }
        
        System.out.println(ans);
    }
    
    // first index where D[i] >= target
    static int lowerBound(long[] D, long target) {
        int lo = 0, hi = D.length;
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (D[mid] < target) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }
}

Submission Info

Judge Result