fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5.  
  6. int convert(vector<int> &arr, int x) {
  7.     return (lower_bound(arr.begin(), arr.end(), x) - arr.begin());
  8. }
  9.  
  10. vector<pair<int, int>> countOccurrences(vector<int> &arr) {
  11.     vector<pair<int, int>> cntcnt;
  12.     for (int i = 0; i < arr.size(); ++i) {
  13.         int temp2 = arr[i];
  14.         int index2 = i;
  15.         int count2 = 0;
  16.         while (temp2 == arr[index2] && index2 < arr.size()) {
  17.             count2++;
  18.             index2++;
  19.         }
  20.         cntcnt.emplace_back(temp2, count2);
  21.         i = index2 - 1;
  22.     }
  23.     return cntcnt;
  24. }
  25.  
  26. void runcase() {
  27.     int n;
  28.     cin >> n;
  29.     vector<int> arr(n);
  30.     for (int i = 0; i < n; ++i) {
  31.         cin >> arr[i];
  32.     }
  33.  
  34.     vector<int> temp = arr;
  35.     vector<int> temp2 = arr;
  36.     vector<int> temp3 = arr;
  37.     sort(temp.begin(), temp.end());
  38.     temp.resize(unique(temp.begin(), temp.end()) - temp.begin());
  39.     for (int i = 0; i < n; ++i) {
  40.         arr[i] = convert(temp, arr[i]);
  41.     }
  42.  
  43.     sort(arr.begin(), arr.end());
  44.     vector<int> arr2 = arr;
  45.     arr.resize(unique(arr.begin(), arr.end()) - arr.begin());
  46.  
  47.     // day ban dau
  48.     cout << "Dãy ban đầu: " << "\n";
  49.     for (int i = 0; i < temp2.size(); ++i) {
  50.         cout << temp2[i] << " ";
  51.     }
  52.     cout << "\n";
  53.     sort(temp3.begin(), temp3.end());
  54.     cout << "Dãy ban đầu sắp xếp: " << "\n";
  55.     for (int i = 0; i < temp3.size(); ++i) {
  56.         cout << temp3[i] << " ";
  57.     }
  58.     cout << "\n";
  59.     cout << "Dãy ban đầu sắp xếp khi rời rạc hóa: " << "\n";
  60.     for (int i = 0; i < arr2.size(); ++i) {
  61.         cout << arr2[i] << " ";
  62.     }
  63.     cout << "\n";
  64.  
  65.     cout << "Dãy ban đầu sắp xếp khi loại phần tử trùng: " << "\n";
  66.     for (int i = 0; i < temp.size(); ++i) {
  67.         cout << temp[i] << " ";
  68.     }
  69.     cout << "\n";
  70.  
  71.     cout << "Dãy ban đầu sắp xếp khi rời rạc hóa và loại phần tử trùng (luôn có dạng 0, 1, 2, 3...): " << "\n";
  72.     for (int i = 0; i < arr.size(); ++i) {
  73.         cout << arr[i] << " ";
  74.     }
  75.     cout << "\n";
  76.  
  77.  
  78.     map<int, long long int> myMap;
  79.     for (int i = 0; i < arr.size(); ++i) {
  80.         myMap[i] = temp[i];
  81.     }
  82.  
  83.     cout << "Mapping giữa dãy ban đầu và rời rạc hóa" << "\n";
  84.     for (int i = 0; i < myMap.size(); ++i) {
  85.         cout << "{" << i << ":" << myMap[i] << "}" << " ";
  86.     }
  87.     cout << "\n";
  88.  
  89.  
  90.     vector<pair<int, int>> cntOcc = countOccurrences(arr2);
  91.     sort(cntOcc.begin(), cntOcc.end());
  92.  
  93.     cout << "Mapping giữa dãy ban đầu và số lượng lặp" << "\n";
  94.     for (int i = 0; i < cntOcc.size(); ++i) {
  95.         cout << "{" << cntOcc[i].first << ":" << cntOcc[i].second << "}" << " ";
  96.     }
  97.     cout << "\n";
  98.  
  99.  
  100.     map<int, long long int> mySumMap;
  101.     for (int i = 0; i < arr.size(); ++i) {
  102.         mySumMap[i] = myMap[i] * cntOcc[i].second;
  103.     }
  104.  
  105.     cout << "Mapping giữa dãy ban đầu và tổng các lặp" << "\n";
  106.     for (int i = 0; i < mySumMap.size(); ++i) {
  107.         cout << "{" << i << ":" << mySumMap[i] << "}" << " ";
  108.     }
  109.     cout << "\n";
  110.  
  111. }
  112.  
  113. int main() {
  114.     runcase();
  115.     return 0;
  116. }
Success #stdin #stdout 0.01s 4652KB
comments (?)
stdin
copy 
8
4 6 6 2 2 2 100 100
stdout
copy 
Dãy ban đầu: 
4 6 6 2 2 2 100 100 
Dãy ban đầu sắp xếp: 
2 2 2 4 6 6 100 100 
Dãy ban đầu sắp xếp khi rời rạc hóa: 
0 0 0 1 2 2 3 3 
Dãy ban đầu sắp xếp khi loại phần tử trùng: 
2 4 6 100 
Dãy ban đầu sắp xếp khi rời rạc hóa và loại phần tử trùng (luôn có dạng 0, 1, 2, 3...): 
0 1 2 3 
Mapping giữa dãy ban đầu và rời rạc hóa
{0:2} {1:4} {2:6} {3:100} 
Mapping giữa dãy ban đầu và số lượng lặp
{0:3} {1:1} {2:2} {3:2} 
Mapping giữa dãy ban đầu và tổng các lặp
{0:6} {1:4} {2:12} {3:200}
https://ideone.com/0oBkKJ
language:
C++ (gcc 8.3)
created:
3 years 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!