Skip to main content
Code Review

Return to Answer

Added more explanation.
Source Link
gam3
gam3
  • 156
  • 3
  • 7

Here is what the data structure looks like if you insert 20 and then 1 through 19. This ends up being 20 writes and 35 moves.

20 
20  1                                                 # add  1 
20  1  2                                              # add  2 
20  3  2  1                                           # add  3, move 1 
20  4  2  1  3                                        # add  4, move 1 
20  4  5  1  3  2                                     # add  5, move 1 
20  4  6  1  3  2  5                                  # add  6, move 1 
20  7  6  4  3  2  5  1                               # add  7, move 2 
20  8  6  7  3  2  5  1  4                            # add  8, move 2 
20  9  6  7  8  2  5  1  4 3                          # add  9, move 2 
20 10  6  7  9  2  5  1  4 3 8                        # add 10, move 2 
20 10 11  7  9  6  5  1  4 3 8 2                      # add 11, move 2 
20 10 12  7  9 11  5  1  4 3 8 2 6                    # add 12, move 2
20 10 13  7  9 11 12  1  4 3 8 2 6 5                  # add 13, move 2
20 10 14  7  9 11 13  1  4 3 8 2 6 5 12               # add 14, move 2
20 15 14 10  9 11 13  7  4 3 8 2 6 5 12 1             # add 15, move 3
20 16 14 15  9 11 13 10  4 3 8 2 6 5 12 1 7           # add 16, move 3
20 17 14 16  9 11 13 10 15 3 8 2 6 5 12 1 7 4         # add 17, move 3
20 18 14 17  9 11 13 10 16 3 8 2 6 5 12 1 7 4 15      # add 18, move 3
20 19 14 17 18 11 13 10 16 9 8 2 6 5 12 1 7 4 15 3    # add 19, move 3

If we just keep the vector ordered then for the worst case we have to move 171 memory locations.

20
20  1
20  2  1                                                       # move  1
20  3  2  1                                                    # move  2
20  4  3  2  1                                                 # move  3
20  5  4  3  2  1                                              # move  4
20  6  5  4  3  2  1                                           # move  5
20  7  6  5  4  3  2  1                                        # move  6
20  8  7  6  5  4  3  2  1                                     # move  7
20  9  8  7  6  5  4  3  2  1                                  # move  8
20 10  9  8  7  6  5  4  3  2  1                               # move  9
20 11 10  9  8  7  6  5  4  3  2  1                            # move 10
20 12 11 10  9  8  7  6  5  4  3  2  1                         # move 11
20 13 12 11 10  9  8  7  6  5  4  3  2  1                      # move 12
20 14 13 12 11 10  9  8  7  6  5  4  3  2  1                   # move 13
20 15 14 13 12 11 10  9  8  7  6  5  4  3  2  1                # move 14
20 16 15 14 13 12 11 10  9  8  7  6  5  4  3  2  1             # move 15
20 17 16 15 14 13 12 11 10  9  8  7  6  5  4  3  2  1          # move 16
20 18 17 16 15 14 13 12 11 10  9  8  7  6  5  4  3  2  1       # move 17
20 19 18 17 16 15 14 13 12 11 10  9  8  7  6  5  4  3  2  1    # move 18

Here is what the data structure looks like if you insert 20 and then 1 through 19. This ends up being 20 writes and 35 moves.

20 
20  1                                                 # add  1 
20  1  2                                              # add  2 
20  3  2  1                                           # add  3, move 1 
20  4  2  1  3                                        # add  4, move 1 
20  4  5  1  3  2                                     # add  5, move 1 
20  4  6  1  3  2  5                                  # add  6, move 1 
20  7  6  4  3  2  5  1                               # add  7, move 2 
20  8  6  7  3  2  5  1  4                            # add  8, move 2 
20  9  6  7  8  2  5  1  4 3                          # add  9, move 2 
20 10  6  7  9  2  5  1  4 3 8                        # add 10, move 2 
20 10 11  7  9  6  5  1  4 3 8 2                      # add 11, move 2 
20 10 12  7  9 11  5  1  4 3 8 2 6                    # add 12, move 2
20 10 13  7  9 11 12  1  4 3 8 2 6 5                  # add 13, move 2
20 10 14  7  9 11 13  1  4 3 8 2 6 5 12               # add 14, move 2
20 15 14 10  9 11 13  7  4 3 8 2 6 5 12 1             # add 15, move 3
20 16 14 15  9 11 13 10  4 3 8 2 6 5 12 1 7           # add 16, move 3
20 17 14 16  9 11 13 10 15 3 8 2 6 5 12 1 7 4         # add 17, move 3
20 18 14 17  9 11 13 10 16 3 8 2 6 5 12 1 7 4 15      # add 18, move 3
20 19 14 17 18 11 13 10 16 9 8 2 6 5 12 1 7 4 15 3    # add 19, move 3

If we just keep the vector ordered then for the worst case we have to move 171 memory locations.

20
20  1
20  2  1                                                       # move  1
20  3  2  1                                                    # move  2
20  4  3  2  1                                                 # move  3
20  5  4  3  2  1                                              # move  4
20  6  5  4  3  2  1                                           # move  5
20  7  6  5  4  3  2  1                                        # move  6
20  8  7  6  5  4  3  2  1                                     # move  7
20  9  8  7  6  5  4  3  2  1                                  # move  8
20 10  9  8  7  6  5  4  3  2  1                               # move  9
20 11 10  9  8  7  6  5  4  3  2  1                            # move 10
20 12 11 10  9  8  7  6  5  4  3  2  1                         # move 11
20 13 12 11 10  9  8  7  6  5  4  3  2  1                      # move 12
20 14 13 12 11 10  9  8  7  6  5  4  3  2  1                   # move 13
20 15 14 13 12 11 10  9  8  7  6  5  4  3  2  1                # move 14
20 16 15 14 13 12 11 10  9  8  7  6  5  4  3  2  1             # move 15
20 17 16 15 14 13 12 11 10  9  8  7  6  5  4  3  2  1          # move 16
20 18 17 16 15 14 13 12 11 10  9  8  7  6  5  4  3  2  1       # move 17
20 19 18 17 16 15 14 13 12 11 10  9  8  7  6  5  4  3  2  1    # move 18
Source Link
gam3
gam3
  • 156
  • 3
  • 7

I would think that a heap would be a better choice of data structure for this problem.

#include <iostream>
#include <vector>
#include <algorithm>

int main (int argc, char const* argv[])
{
    int n, k;
    std::cin >> n >> k;
    std::vector<int> v;
    std::make_heap (v.begin(), v.end());
    while (k && n) {
        int a;
        std::cin >> a;
        if (a == -1) {
            k--;
            int x = v.front();
            std::cout << x << '\n';
            std::pop_heap(v.begin(),v.end()); v.pop_back();
        } else {
            n--;
            v.push_back(a); std::push_heap(v.begin(),v.end());
        }
    }
    return 0;
}