Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.*;
- import java.lang.reflect.Array;
- import java.math.*;
- import java.util.*;
- public class Main {
- static final long MOD = 998244353;
- public static void main(String[] args) throws IOException {
- FastScanner sc=new FastScanner();
- int N = sc.nextInt();
- int K = sc.nextInt();
- //int N = 200000;
- //int K = 200000;
- ArrayList<Integer> nums = new ArrayList();
- for (int i = 0; i < N; i++) {
- nums.add(sc.nextInt());
- //nums[i] = 200000;
- }
- //long t1 = System.currentTimeMillis();
- Collections.sort(nums);
- int[] sumToHit = new int[200001];
- int[] Kleft = new int[200001];
- for (int i = 0; i <= 200000; i++) {
- Kleft[i] = K;
- }
- for (int num: nums) {
- int key = num;
- int steps = 0;
- while (key > 0) {
- if (Kleft[key] > 0) {
- sumToHit[key] += steps;
- Kleft[key] -= 1;
- }
- key = key/2;
- steps++;
- }
- if (Kleft[0] > 0) {
- sumToHit[0] += steps;
- Kleft[0] -= 1;
- }
- }
- int bestCost = Integer.MAX_VALUE;
- for (int i = 0; i <= 200000; i++) {
- if (Kleft[i] == 0) {
- bestCost = Math.min(bestCost, sumToHit[i]);
- }
- }
- System.out.println(bestCost);
- //long t2 = System.currentTimeMillis();
- //System.out.println(t2-t1);
- }
- static class FastScanner {
- BufferedReader br;
- StringTokenizer st;
- public FastScanner()
- {
- br = new BufferedReader(new
- InputStreamReader(System.in));
- }
- String next()
- {
- while (st == null || !st.hasMoreElements())
- {
- try
- {
- st = new StringTokenizer(br.readLine());
- }
- catch (IOException e)
- {
- e.printStackTrace();
- }
- }
- return st.nextToken();
- }
- int nextInt()
- {
- return Integer.parseInt(next());
- }
- long nextLong()
- {
- return Long.parseLong(next());
- }
- double nextDouble()
- {
- return Double.parseDouble(next());
- }
- String nextLine()
- {
- String str = "";
- try
- {
- str = br.readLine();
- }
- catch (IOException e)
- {
- e.printStackTrace();
- }
- return str;
- }
- }
- }
- class Node {
- public int n;
- public HashSet<Node> children;
- public Node(int n) {
- this.n = n;
- children = new HashSet<Node>();
- }
- public void addChild(Node node) {
- children.add(node);
- }
- }
- class BinaryIndexedTree {
- public long[] arr;
- public BinaryIndexedTree (int N) {
- arr = new long[N+1];
- arr[0] = 0;
- }
- //add k to the i-th element.
- public void add(long k, int i) {
- int node = i+1;
- while (node < arr.length) {
- arr[node] += k;
- node += node & (-node);
- }
- }
- //sum up the elements from input[s_i] to input[e_i], from [s_i,e_i).
- public long sum(int s_i, int e_i) {
- return sum(e_i) - sum(s_i);
- }
- public long sum(int i) {
- long total = 0;
- int node = i;
- while (node > 0) {
- total += arr[node];
- node -= node & (-node);
- }
- return total;
- }
- }
Add Comment
Please, Sign In to add comment