fork download
copy 
  1. import java.util.*;
  2.  
  3. class Main {
  4.  
  5.     public static void main(String[] args) {
  6.         Scanner sc = new Scanner(System.in);
  7.  
  8.         // Input size n
  9.         int n = sc.nextInt();
  10.  
  11.         // Input array
  12.         int[] b = new int[n];
  13.         for (int i = 0; i < n; i++) {
  14.             b[i] = sc.nextInt();
  15.         }
  16.  
  17.         // Count frequencies using TreeMap sorted descending
  18.         TreeMap<Integer, Integer> k = new TreeMap<>(Collections.reverseOrder());
  19.         for (int i = 0; i < n; i++) {
  20.             k.put(b[i], k.getOrDefault(b[i], 0) + 1);
  21.         }
  22.  
  23.         // Copy frequency values into an array
  24.  
  25.         int m = k.size();
  26.         int[] freq = new int[m];
  27.         int idx = 0;
  28.         for (Map.Entry<Integer, Integer> e : k.entrySet()) {
  29.             freq[idx++] = e.getValue();
  30.         }
  31.  
  32.         // Apply merging logic
  33.         int step = 0;
  34.         for (int i = 0; i < m - 1; i++) {
  35.             step += freq[i];        // cost of moving frequency
  36.             freq[i + 1] += freq[i]; // merge into next
  37.         }
  38.  
  39.         // Print result
  40.         System.out.println(step);
  41.  
  42.         sc.close();
  43.     }
  44. }
  45.  
Success #stdin #stdout 0.12s 54640KB
comments (?)
stdin
copy 
5
4 5 5 2 4
stdout
copy 
6
https://ideone.com/PU1MBD
language:
Java (HotSpot 12)
created:
10 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!