The structure of the train dispatching track at the railway station is shown in the figure below.
There is an entrance track and an exit track at both ends, and there are N parallel tracks between them. Each train can choose any track to enter from the entrance and finally leave from the exit. There are 9 trains in the picture, waiting to enter in the order {8, 4, 2, 5, 3, 9, 1, 6, 7} at the entrance. If they are required to leave the exit in descending order, how many parallel rails are needed for scheduling?
Input format:
The first line of input gives an integer N (2 ≤ N ≤105), and the next line gives an integer number from 1 to N A rearrangement. Separate numbers with spaces.
Output format:
Output in one line the minimum number of rails required to move the input trains away from them in descending order of sequence numbers.
Input sample:
9
8 4 2 5 3 9 1 6 7
Example output:
4
Let’s analyze the question first. We can know that the train numbers coming in from the left are random, but when these trains leave from the right, we have to ensure that they are from large to small< /strong>Leave in turn.
It looks complicated at first glance, so we can think about simplifying it.
Between the left and the right, there are scheduling rails we designed for these trains. Each rail can park any car. At the same time, we can also divide the process from left to right into two step:
1. The train enters thedispatch track from the left.
2.The train leaves from the right onthe dispatch track.
It is not difficult for us to find that because we are required to let the trains leave in order from large to small in the end, we must make the trains sort from small to large on the dispatching track, otherwise there will be a situation of “small ones suppressing large ones”, and they will be ” The large serial number train that is suppressed will never be able to get out. As follows:
So we must ensure that when entering the dispatch track from the left, the trains on the dispatch track are arranged from small to large.
After multiple tracks with ascending train numbers are arranged in parallel, we can ensure that the last train leaving from the right leaves in order from large to small. We only need to select all dispatching tracks each time< strong>The one with the largest train number is sufficient. (However, this problem is outside the scope of our discussion, we only need to prove how many scheduling tracks are needed).
So our problem is once again simplified.
We only need to consider the first step: the train enters the scheduling track from the left, and on all scheduling tracks, the train numbers are arranged from small to large.
Let’s simulate it: if a train enters the dispatch track from the left, it has two choices:
1. Enter the track where there is already a train and queue up behind him.
2. Create a new track.
Obviously, the basis for judgment is whether the serial numbers of our two trains are greater than the last train on the track that already has trains (it is also the train with the smallest serial number on this track) The serial number, If there is a tail car with a larger serial number than ours, we can follow it as a matter of course, and if all the tail cars have a smaller serial number than ours, it will exist on any track. The small is suppressing the big, then we can only open up a new track.
It is worth mentioning that if there are more than two tail cars with larger serial numbers than ours, we need to follow the one with the smallest serial number among them. For example, if our car is 6 , the two tail cars are 7 and 9, we need to follow 7, this is because we need to prepare for the possible 8Be prepared. If 6 is behind 9, then when 8 appears we have to open a new track (it might have been There is no need to open), which may make our final answer wrong.
So how to find the serial number of this tail car?
I believe that smart friends have thought of —set since they just mentioned the order issue.
Moreover, in the previous article introducing set (STL container (2)-set_hanbaor’s blog-CSDN blog), I also introduced two functions:
lower_bound(key_value) returns the first locator that is greater than or equal to key_value. If it does not exist, return end();
upper_bound(key_value), returns the first locator that is greater than key_value. If it does not exist, return end();
Each serial number in the question is different. The two functions have the same effect in this code. I used the former.
Okay, let’s get to the code here.
#include <iostream>
#include <set>
using namespace std;
int main()
{
int n,m;
cin>>n;
set<int> st;
for(int i=0;i<n;i + + )
{
cin>>m;
if(st.lower_bound(m)!=st.end())//Determine whether there is a tail car with a serial number greater than the entering car
{
st.erase(st.lower_bound(m));//If it exists, let the original tail car leave first
}
st.insert(m); //Regardless of whether the tail car exists or not, the new train needs to enter the track
//This is actually easy to understand. If you can follow the tail car, the original tail car goes out and the new train comes in, the size of the set is equivalent to not changing.
//If the tail car that meets the conditions does not exist, let the new car enter the track directly. At this time, the size of the set will be increased by 1, which means a new track is opened.
}
cout<<st.size()<<endl;
return 0;
\t
}
Is the code unexpectedly short?
Let’s savor it and appreciate the wonder of these few lines.
Taking the example as an example, the first three numbers 8, 4, and 2 are exactly a perfect sequence.
8: The first number, directly open a new track to enter.
4: Through lower_bound(4), you can get 8, so enter the if statement and use let erase to let 8 leave. At the same time, insert (4), here is the first meaning of this statement: Let the element enter with the car.
2: The same as 4, so no further details will be given.
5: A special situation occurs. At this time, there are only 2 in our set container. Obviously 2<5, so we cannot enter the if statement and insert (5) directly. Here is the second meaning of this statement: When you can’t follow the car in, open a new track
This is what I wrote in the code comments. Whether it is following a car or opening a new track, this new car must enter the schedule, so the insert statement must be executed.
3: There are 2 and 5 in the set at this time. 3 can only choose to push 5 away.
9: The largest number, which can only open up new tracks.
1: The smallest number. A special situation occurs again. At this time, there are three numbers 2, 3, and 9 in the set. Each number is larger than 1. Remember
What does lower_bound(key_value) do? It returns the first locator that is greater than or equal to key_value. So at this time, our 1 cleverly defeated 2,
6: At this time, there are three numbers in the set: 1, 3, and 9. 6 can only defeat 9.
7: At this time, there are three numbers 1, 3, and 6 in the set, and 7 opens a new track.
Finally, our set container is 1, 3, 6, 7.
Its size() is 4,
Got the solution
Passed all pta points:
over
The knowledge points of the article match the official knowledge files, and you can further learn related knowledge. Algorithm skill tree Home page Overview 56830 people are learning the system