Cerinta completa

Bill Gates is on one of his philanthropic journeys to a village in Utopia. He has brought a box of packets of candies and would like to distribute one packet to each of the children. Each of the packets contains a number of candies. He wants to minimize the cumulative difference in the number of candies in the packets he hands out. This is called the unfairness sum. Determine the minimum unfairness sum achievable.

For example, he brings packets where the number of candies is . There are children. The minimum difference between all packets can be had with from indices and . We must get the difference in the following pairs: . We calculate the unfairness sum as:

packets candies				
0	3		indices		difference	result
1	3		(0,1),(0,2)	|3-3| + |3-4|	1 
2	4		(1,2)		|3-4|		1

Total = 2

Function Description

Complete the angryChildren function in the editor below. It should return an integer that represents the minimum unfairness sum achievable.

angryChildren has the following parameter(s):

  • k: an integer that represents the number of children
  • packets: an array of integers that represent the number of candies in each packet

Input Format

The first line contains an integer .
The second line contains an integer .
Each of the next lines contains an integer .

Constraints



Output Format

A single integer representing the minimum achievable unfairness sum.

Sample Input 0 

7
3
10
100
300
200
1000
20
30

Sample Output 0 

40

Explanation 0

Bill Gates will choose packets having 10, 20 and 30 candies. The unfairness sum is .

Sample Input 1 

10
4
1
2
3
4
10
20
30
40
100
200

Sample Output 1 

10

Explanation 1

Bill Gates will choose 4 packets having 1,2,3 and 4 candies. The unfairness sum i .

Limbajul de programare folosit: java8

Cod:

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

public class Solution {
    private static class FastScanner {
        private final InputStream in;
        private final byte[] buffer = new byte[1 << 16];
        private int ptr = 0, len = 0;
        FastScanner(InputStream is) { this.in = is; }
        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
                if (len <= 0) return -1;
            }
            return buffer[ptr++];
        }
        long nextLong() throws IOException {
            int c;
            do { c = read(); } while (c <= ' ' && c != -1);
            int sign = 1;
            if (c == '-') { sign = -1; c = read(); }
            long val = 0;
            while (c > ' ') {
                val = val * 10 + (c - '0');
                c = read();
            }
            return sign == 1 ? val : -val;
        }
        int nextInt() throws IOException { return (int) nextLong(); }
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);
        int n = fs.nextInt();
        int k = fs.nextInt();
        long[] a = new long[n];
        for (int i = 0; i < n; i++) a[i] = fs.nextLong();
        Arrays.sort(a);

        if (k <= 1) {
            System.out.println(0);
            return;
        }

        long sum = 0;
        for (int i = 0; i < k; i++) sum += a[i];

        long unfair = 0;
        for (int i = 0; i < k; i++) {
            unfair += a[i] * (2L * i - k + 1L);
        }

        long best = unfair;

        for (int l = 0; l + k < n; l++) {
            long x = a[l];
            long y = a[l + k];
            long rem = (sum - x) - x * (k - 1L);
            long add = y * (k - 1L) - (sum - x);
            unfair = unfair - rem + add;
            sum = sum - x + y;
            if (unfair < best) best = unfair;
        }

        System.out.println(best);
    }
}

Scor obtinut: 1.0

Submission ID: 464617503

Link challenge: https://www.hackerrank.com/challenges/angry-children-2/problem

Angry Children 2