Draw Your Cards

Original link

topic description

The existing n cards are stacked together, each time one card is taken from the top (the value above is x), and placed face up on the table, the placement rules are:

Find the first >=x card already on the table, stack it on top (update the value there)
If it finds a card that meets the requirements every day, open a new pile (single card)
If the number of cards revealed in a certain pile reaches k, this pile can be taken away

In the order of card number 1-n, output when the card was taken, and output -1 for cards that were not taken away

Sample input

5 23 5 2 1 4

Sample output

433-14

---

Algorithms

(chain storage + binary search)

Simulation.set maintains the number of cards in each pile and the value of the top card
binary search value to achieve update

There is a point that is not very easy to deal with, that is, how to find the path when taking k cards?
Then you can use an array to iterate and save the path (a bit like a linked list, look back)

And because the cards are taken in order, they can be processed online

Note: Use the lower_bound that comes with the set, which is much more efficient than the lower_bound of the header file

C++ code

Time Complexity$O(nlogn)$

#include #include #include #include #include using namespace std;typedef pair PII;int main(){int n,k;scanf("%d%d",&n,&k);vector card(n + 10,-1),cnt(n + 10,0),store(n + 10,-1);set s;for (int i = 1; i <= n; i ++ ) {int p;scanf("%d",&p);auto key = s.upper_bound(p);//Be sure to use the upper_bound that comes with the setif (key == s.end()) {//end is the next to the lasts.insert(p);cnt[p] = 1;}else {//Only the top value is stored, and the pointer is used to store the following valuestore[p] = (*key);cnt[p] = cnt[(*key)] + 1;s.erase(key);s.insert(p);}if (cnt[p] == k) {s.erase(p);int x = p;for(int j = 0;j < k;j++){card[x] = i;x = store[x];//Iterate over the stored values ​​below}}}for (int i = 1;i <= n;i ++ ) printf("%d\n",card[i]);return 0;}