fork(1) download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3.  
  4. int GetIntValueFromUser() {
  5.   int value = 0;
  6.   std::cin >> value;
  7.   return value;
  8. }
  9.  
  10. std::vector<int> GetFirstQueueOfValuesFromUser(int number_of_values) {
  11.   std::vector<int> first_window(number_of_values);
  12.   std::generate(std::begin(first_window), std::end(first_window),
  13.                 GetIntValueFromUser);
  14.   return first_window;
  15. }
  16.  
  17. std::vector<int> GetSortedQueue(const std::vector<int>& unsorted_queue) {
  18.   std::vector<int> sorted_queue(unsorted_queue.size());
  19.   std::partial_sort_copy(std::begin(unsorted_queue), std::end(unsorted_queue),
  20.                          std::begin(sorted_queue), std::end(sorted_queue));
  21.   return sorted_queue;
  22. }
  23.  
  24. int GetMinFromSortedQueue(const std::vector<int>& sorted_queue) {
  25.   return sorted_queue.front();
  26. }
  27.  
  28. void ShowMinOfSortedQueue(const std::vector<int>& sorted_queue) {
  29.   std::cout << GetMinFromSortedQueue(sorted_queue) << '\n';
  30. }
  31.  
  32. void SwapValues(std::vector<int>& sorted_queue, int old_value, int new_value) {
  33.   sorted_queue.erase(std::lower_bound(std::begin(sorted_queue),
  34.                                       std::end(sorted_queue), old_value));
  35.   sorted_queue.insert(std::lower_bound(std::begin(sorted_queue),
  36.                                        std::end(sorted_queue), new_value),
  37.                       new_value);
  38. }
  39.  
  40. int main() {
  41.   size_t n = GetIntValueFromUser();
  42.   size_t k = GetIntValueFromUser();
  43.   auto queue = GetFirstQueueOfValuesFromUser(k);
  44.   auto sorted_queue = GetSortedQueue(queue);
  45.   ShowMinOfSortedQueue(sorted_queue);
  46.   for (size_t i = 0; i < n - k; ++i) {
  47.     auto new_value_from_user = GetIntValueFromUser();
  48.     auto oldest_position = i % queue.size();
  49.     auto oldes_value_from_user = queue[oldest_position];
  50.     SwapValues(sorted_queue, oldes_value_from_user, new_value_from_user);
  51.     ShowMinOfSortedQueue(sorted_queue);
  52.     std::swap(queue[oldest_position], new_value_from_user);
  53.   }
  54. }
  55.  
Success #stdin #stdout 0s 3236KB
comments (?)
stdin
copy 
8 2
5 3 9 -1 0 7 4 2
stdout
copy 
3
3
-1
-1
0
4
2
https://ideone.com/gvhbqT
language:
C++14 (gcc 8.3)
created:
11 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!