Falling ant

Falling ants

Title Description ：
The length of one is 1 There are some ants crawling on Mi's stick . They go at a speed of one centimeter per second or are stationary , There are only two directions , Left or right . If two ants meet , Then they immediately exchange speed and continue to crawl . Three ants meet , Then the ants on both sides exchange speed , The ant in the middle is still static . If they get to the edge of the stick （0 or 100 Cm ） And fall off the stick . At a certain moment, the position of the ant is different, and it is in an integral centimeter （ namely 1,2,3,…99 centimeter ）, There is only one ant A Speed is 0, Other ants are crawling to the left or right . Give the position and initial velocity of all ants on the stick at that time , Find the ants A From this moment to the time it takes to fall .

Input description :
The first line contains an integer representing the number of ants N（2<=N<=99）, After that, we have N That's ok , Each line describes the initial state of an ant . Each initial state consists of two integers , Space separates the middle , The first number is the number of centimeters in the initial position P（1<=P<=99）, The second number represents the initial direction ,-1 Indicating left ,1 Indicating right ,0 Stand still .

Output description ：
Ant A The time from the start to the fall . If it doesn't fall , Output “Cannot fall!”

Input ：
4
10 1
90 0
95 -1
98 -1
Output ：
98

Answer key ： The ultimate goal of this question is to understand , An ant can only move within the range delineated by his left and right ants , That is to say, no matter how you exercise , The relative order of these ants on the stick is unchanged .

First of all, the meaning of exchange speed is not just the size of exchange speed , At the same time, the direction is also changed . That is to say, the ants will not cross each other after they meet , It's moving in the opposite direction . It can be understood as ： No one can get past each other , All ants can only be found in the area composed of two ants “ prisoner 's cage ” Internal movement .
Find a speed of 0 The ants of
On its left left An ant
On the right right An ant
If it is judged that the ant finally falls to the left , Then it must be the left+1 One fell
If you fall to the right , Then it must be the second right+1 One fell

How to judge which side to fall from ？
Suppose the ants that go left have toleft individual
The ant that walks to the right toright individual
First of all, understand Last, last There will be toleft An ant fell from the left ,toright Ants fall from the right .

If the number of all ants walking to the left toleft Greater than left So the one on the left of the static ant left All of them fell down , At this time, there are ants to fall from the left , Then it's the static ant's turn

If the number of all ants walking to the right toright Greater than right So the one on the right of the static ant right All of them fell down , At this time, there are ants to fall from the right , Then it's the static ant's turn .

If an ant walks to the left toleft be equal to left Then it is impossible for a static ant to jump down
If an ant walks to the right toright be equal to right Then it is impossible for a static ant to jump down

Now it is clear that if we judge which side to jump from , So how to calculate the time
If you jump from the left , So it can be considered as one of the ants walking to the left , Subscript to be left It's the time for the ants to go from the starting position to the leftmost position

If you jump from the right , So it can be considered as one of the ants walking to the right ,（right=n-1-left） Subscript to be n-left-1 It's the time when the ants from the starting position go to the far right .


The following is the reference code ：

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
 
struct Ant
{
    
    int position;
    int direct;    // Direction 
};
bool cmp(Ant a,Ant b)
{
    
    return a.position<b.position;
}
 
int main()
{
    
    int n;
    while(scanf("%d",&n) != EOF)
    {
    
        vector<Ant> ant(n);
        for(int i = 0; i<n; i++)
            scanf("%d %d",&ant[i].position,&ant[i].direct);
        sort(ant.begin(),ant.end(),cmp);
        // The next thing to do is to find the position of the stationary one , To do this, we have to sort 
        // In this way, a few ants to the left of the static ants came out 
        int target,toLeft = 0;    // Here we choose the left as the benchmark 
        for(int i = 0; i<n; i++)    // Traverse all the ants 
        {
    
            if(ant[i].direct == 0)
                target = i;
            if(ant[i].direct == -1)
                toLeft++;
        }// current target That's the number on the left side of the static ant , That is, the subscript of the static ant 
        bool flag = false;
        int ans;
        if(toLeft == target)
            flag = true;
        else if (toLeft > target)// So what we're looking for is all the ants that are going left , The table below for target The ants of 
        {
    
            int cnt = 0;// Counter 
            for(int i = 0; i<n; i++)
            {
    
                if(ant[i].direct == -1 && cnt == target)
                {
    
                    ans = ant[i].position;// The location of this ant , The time it takes to fall , That is, ants A The time of the fall 
                    break;
                }
                else if(ant[i].direct == -1)
                    cnt++;
            }
        }
        else    // Fewer ants walk to the left , So the target ant will fall to the right 
        {
    
            int cnt = 0;
            for(int i = n - 1; i>=0; i--)
            {
    
                if(ant[i].direct == 1 && cnt == n - target - 1)// Corresponding changes ,cnt To become a static ant, the number of ants on the right side 
                {
    
                    ans = 100 - ant[i].position; // Because it is to the right , Just use 100 Cut it 
                    break;
                }
                else if(ant[i].direct == 1)
                    cnt++;
            }
        }
        if(flag)
            printf("Cannot fall!\n");
        else
            printf("%d\n",ans);
    }//while
    return 0;
}

It took a long time to figure it out , Before you forget , Write it down .