fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main() 
  5. {
  6.     // index    1   2    3   4   5  6   7   8   9
  7.     int b[10] = {0, 5 , 5 , 5 , 3 , 3 , 2 , 2 , 1 , 1};
  8.     int n = 9;
  9.  
  10.     /*
  11.     Element , frequency 
  12.            5             3   --> index 3
  13.            3             2   --> index 2
  14.            2             2   --> index 1
  15.            1             2   --> index 0
  16.     */
  17.  
  18.     unordered_map<int,int>k;
  19.  
  20.     for(int i=1; i<=n; i++)
  21.     {
  22.         k[b[i]] = k[b[i]] + 1;
  23.     }
  24.  
  25.     /*
  26.       <(5,3)<5 , 3>>g; // g(5,3)
  27.       <(3,2)<3 , 2>g; // g(3,2)
  28.       <(2,2)<2 , 2>g; // g(2,2)
  29.       <(1,2)<1 , 2>g; // g(1,2)
  30.     */
  31.  
  32.     vector<pair<int,int>>g;
  33.  
  34.     for(auto u=k.begin(); u!=k.end(); u++)
  35.     {
  36.         //                     Element  Frequency
  37.         g.push_back({u->first, u->second});
  38.     }
  39.  
  40.     int size = g.size(); // map size -> 4
  41.     int step = 0;
  42.  
  43.     for(int i=size - 1; i>=1; i--)
  44.     {
  45.         // iteration 3:
  46.         // 4 - 1 = 3
  47.         // i = 3
  48.         //
  49.         // g[i-1].second = g[3-1].second = g[2].second
  50.         // g[2].second = 2 (frequency of element 3)
  51.         //
  52.         // g[i].second = g[3].second
  53.         // g[3].second = 3 (frequency of element 5)
  54.         //
  55.         // g[2].second = g[2].second + g[3].second
  56.         // g[2].second = 2 + 3 = 5
  57.         //
  58.         // step = 0
  59.         // step = step + g[3].second
  60.         // step = 0 + 3 = 3
  61.         //
  62.         // We reset the frequency at index 3 to zero because
  63.         // its frequency has already been transferred to index 2.
  64.         //
  65.         // map now becomes {2, 2, 5, 0}
  66.  
  67.  
  68.         // iteration 2:
  69.         // 3 - 1 = 2
  70.         // i = 2
  71.         //
  72.         // g[i-1].second = g[2-1].second = g[1].second
  73.         // g[1].second = 2 (frequency of element 2)
  74.         //
  75.         // g[i].second = g[2].second
  76.         // g[2].second = 5 (updated frequency of element 3)
  77.         //
  78.         // g[1].second = g[1].second + g[2].second
  79.         // g[1].second = 2 + 5 = 7
  80.         //
  81.         // step = 3
  82.         // step = step + g[2].second
  83.         // step = 3 + 5 = 8
  84.         //
  85.         // We reset the frequency at index 2 to zero because
  86.         // its frequency has already been transferred to index 1.
  87.         //
  88.         // map now becomes {2, 7, 0, 0}
  89.  
  90.  
  91.         // iteration 1:
  92.         // 2 - 1 = 1
  93.         // i = 1
  94.         //
  95.         // g[i-1].second = g[1-1].second = g[0].second
  96.         // g[0].second = 2 (frequency of element 1)
  97.         //
  98.         // g[i].second = g[1].second
  99.         // g[1].second = 7 (updated frequency of element 2)
  100.         //
  101.         // g[0].second = g[0].second + g[1].second
  102.         // g[0].second = 2 + 7 = 9
  103.         //
  104.         // step = 8
  105.         // step = step + g[1].second
  106.         // step = 8 + 7 = 15
  107.         // We reset the frequency at index 1 to zero because
  108.         // its frequency has already been transferred to index 0.
  109.         //
  110.         // map now becomes {9, 0, 0, 0}
  111.  
  112.  
  113.         //       previous index element freq   current index element freq
  114.         g[i-1].second = g[i-1].second + g[i].second;
  115.  
  116.         step = step + g[i].second;
  117.  
  118.         g[i].second = 0;
  119.     }
  120.  
  121.     cout << step << endl;
  122.  
  123.     return 0;
  124. }
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
14
https://ideone.com/uCRona
language:
C++ (gcc 8.3)
created:
2 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!