Advertisement
konchin_shih

d713: 中位数

Aug 7th, 2020
85
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.88 KB | None | 0 0
  1. #include<iostream>
  2. #include<queue>
  3. #include<vector>
  4. #include<limits>
  5. #define endl '\n'
  6. using namespace std;
  7. int main() {
  8.     cin.tie(nullptr);
  9.     ios::sync_with_stdio(false);
  10.     priority_queue<long long, vector<long long>,    less<long long>> l;
  11.     priority_queue<long long, vector<long long>, greater<long long>> r;
  12.     l.emplace(numeric_limits<long long>::min());
  13.     r.emplace(numeric_limits<long long>::max());
  14.     int n, cnt = 0;
  15.     auto sort = [](auto & v) {
  16.         for (size_t i = 0; i < v.size(); i++)
  17.             for (size_t j = i; j < v.size(); j++)
  18.                 if (v[i] > v[j]) swap(v[i], v[j]);
  19.     };
  20.     while (cin >> n) {
  21.         vector<long long> v{l.top(), r.top(), n};
  22.         sort(v), l.pop(), r.pop();
  23.         if ((++cnt) & 1)
  24.             l.emplace(v[0]), l.emplace(v[1]), r.emplace(v[2]), cout << l.top() << endl;
  25.         else
  26.             l.emplace(v[0]), r.emplace(v[1]), r.emplace(v[2]), cout << (l.top() + r.top()) / 2 << endl;
  27.     }
  28.     return 0;
  29. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement