SHARE
TWEET

Untitled

a guest Aug 30th, 2019 17 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.io.*;
  2. import java.lang.reflect.Array;
  3. import java.math.*;
  4. import java.util.*;
  5.  
  6. public class Main {
  7.     static final long MOD = 998244353;
  8.     public static void main(String[] args) throws IOException {
  9.         FastScanner sc=new FastScanner();
  10.         int N = sc.nextInt();
  11.         int K = sc.nextInt();
  12.         //int N = 200000;
  13.         //int K = 200000;
  14.         ArrayList<Integer> nums = new ArrayList();
  15.         for (int i = 0; i < N; i++) {
  16.             nums.add(sc.nextInt());
  17.             //nums[i] = 200000;
  18.         }
  19.         //long t1 = System.currentTimeMillis();
  20.         Collections.sort(nums);
  21.         int[] sumToHit = new int[200001];
  22.         int[] Kleft = new int[200001];
  23.         for (int i = 0; i <= 200000; i++) {
  24.             Kleft[i] = K;
  25.         }
  26.  
  27.         for (int num: nums) {
  28.             int key = num;
  29.             int steps = 0;
  30.             while (key > 0) {
  31.                 if (Kleft[key] > 0) {
  32.                     sumToHit[key] += steps;
  33.                     Kleft[key] -= 1;
  34.                 }
  35.                 key = key/2;
  36.                 steps++;
  37.             }
  38.             if (Kleft[0] > 0) {
  39.                 sumToHit[0] += steps;
  40.                 Kleft[0] -= 1;
  41.             }
  42.         }
  43.  
  44.         int bestCost = Integer.MAX_VALUE;
  45.         for (int i = 0; i <= 200000; i++) {
  46.             if (Kleft[i] == 0) {
  47.                 bestCost = Math.min(bestCost, sumToHit[i]);
  48.             }
  49.         }
  50.         System.out.println(bestCost);
  51.         //long t2 = System.currentTimeMillis();
  52.         //System.out.println(t2-t1);
  53.     }
  54.  
  55.     static class FastScanner {
  56.         BufferedReader br;
  57.         StringTokenizer st;
  58.  
  59.         public FastScanner()
  60.         {
  61.             br = new BufferedReader(new
  62.                     InputStreamReader(System.in));
  63.         }
  64.  
  65.         String next()
  66.         {
  67.             while (st == null || !st.hasMoreElements())
  68.             {
  69.                 try
  70.                 {
  71.                     st = new StringTokenizer(br.readLine());
  72.                 }
  73.                 catch (IOException  e)
  74.                 {
  75.                     e.printStackTrace();
  76.                 }
  77.             }
  78.             return st.nextToken();
  79.         }
  80.  
  81.         int nextInt()
  82.         {
  83.             return Integer.parseInt(next());
  84.         }
  85.  
  86.         long nextLong()
  87.         {
  88.             return Long.parseLong(next());
  89.         }
  90.  
  91.         double nextDouble()
  92.         {
  93.             return Double.parseDouble(next());
  94.         }
  95.  
  96.         String nextLine()
  97.         {
  98.             String str = "";
  99.             try
  100.             {
  101.                 str = br.readLine();
  102.             }
  103.             catch (IOException e)
  104.             {
  105.                 e.printStackTrace();
  106.             }
  107.             return str;
  108.         }
  109.     }
  110. }
  111.  
  112. class Node {
  113.     public int n;
  114.     public HashSet<Node> children;
  115.  
  116.     public Node(int n) {
  117.         this.n = n;
  118.         children = new HashSet<Node>();
  119.     }
  120.  
  121.     public void addChild(Node node) {
  122.         children.add(node);
  123.     }
  124. }
  125.  
  126. class BinaryIndexedTree {
  127.     public long[] arr;
  128.  
  129.     public BinaryIndexedTree (int N) {
  130.         arr = new long[N+1];
  131.         arr[0] = 0;
  132.     }
  133.  
  134.     //add k to the i-th element.
  135.     public void add(long k, int i) {
  136.         int node = i+1;
  137.         while (node < arr.length) {
  138.             arr[node] += k;
  139.             node += node & (-node);
  140.         }
  141.     }
  142.  
  143.     //sum up the elements from input[s_i] to input[e_i], from [s_i,e_i).
  144.     public long sum(int s_i, int e_i) {
  145.         return sum(e_i) - sum(s_i);
  146.     }
  147.  
  148.     public long sum(int i) {
  149.         long total = 0;
  150.         int node = i;
  151.         while (node > 0) {
  152.             total += arr[node];
  153.             node -= node & (-node);
  154.         }
  155.         return total;
  156.     }
  157. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top