fork download
copy 
  1. #include <iostream>
  2. #include <map>
  3. #include <vector>
  4. using namespace std;
  5.  
  6. int main() {
  7.     int n;
  8.     cin >> n;  // Input size of the array (excluding b[0])
  9.  
  10.     vector<int> b(n + 1, 0);  // Initialize the b array of size n + 1, with all elements 0
  11.     map<int, int> k;  // Map to store frequency of elements
  12.  
  13.     // Input array b (index 1 to n)
  14.     for (int i = 1; i <= n; i++) {
  15.         cin >> b[i];  // Input each element of b
  16.     }
  17.  
  18.     // Count frequency of each element in b
  19.     for (int i = 1; i <= n; i++) {
  20.         k[b[i]] += 1;  // Increment frequency of b[i] in map k
  21.     }
  22.  
  23.     // Create a vector of pairs to store (element, frequency)
  24.     vector<pair<int, int>> g;
  25.     for (auto u : k) {
  26.         g.push_back({u.first, u.second});  // Insert element and its frequency into vector g
  27.     }
  28.  
  29.     int size = g.size();
  30.     int step = 0;  // Initialize step variable to 0
  31.  
  32.     // Traverse the vector g backward and calculate the steps
  33.     for (int i = size - 1; i >= 1; i--) {
  34.         g[i - 1].second += g[i].second;  // Add frequency of g[i] to g[i-1]
  35.         step += g[i].second;  // Increment step by the frequency of g[i]
  36.         g[i].second = 0;  // Reset frequency of g[i] to 0
  37.     }
  38.  
  39.     // Output the result
  40.     cout << step << endl;
  41.  
  42.     return 0;
  43. }
  44.  
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
7
3 2 3 4 4 7 6
stdout
copy 
13
https://ideone.com/cb74Th
language:
C++ (gcc 8.3)
created:
2 days 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!