Advertisement
pasholnahuy

Хоффман длина кода

Sep 28th, 2023
1,178
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.86 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <set>
  4. using namespace std;
  5.  
  6.  
  7. int main() {
  8.     int n;
  9.     cin >> n;
  10.     vector<int> vec(n);
  11.     vector<int> depth(n, 0);
  12.     set<pair<int, vector<int>>> temp;
  13.     for (int i = 0; i < n; ++i){
  14.         cin >> vec[i];
  15.         temp.insert({vec[i], {i}});
  16.     }
  17.     for (int i = 0; i < n - 1; ++i){
  18.         auto el1 = *temp.begin();
  19.         temp.erase(temp.begin());
  20.         auto el2 = *temp.begin();
  21.         temp.erase(temp.begin());
  22.         for (auto ind: el1.second){
  23.             ++depth[ind];
  24.         }
  25.         for (auto ind: el2.second){
  26.             ++depth[ind];
  27.             el1.second.push_back(ind);
  28.         }
  29.         el1.first += el2.first;
  30.         temp.insert(el1);
  31.     }
  32.     int ans = 0;
  33.     for (int i = 0; i < n; ++i){
  34.         ans += vec[i] * depth[i];
  35.     }
  36.     cout << ans;
  37.     return 0;
  38. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement