坠落的蚂蚁

#!/usr/bin/python
#-*- coding:utf-8 -*-

#Author: Ben

stickLength = 100
while True:
    try:
        N = input()
        postions = [0]*N
        speeds = [0]*N
        numLeft = numRight = posA = 0
        leftValidAnts = []
        rightValidAnts = []

        for i in range(N):
            p, d = map(int, raw_input().strip().split())
            postions[i] = p
            speeds[i] = d
            if d == 0:
                posA = p

        for i in range(N):
            if postions[i]<posA and speeds[i]>0:
                leftValidAnts.append(stickLength-postions[i])
                numLeft += 1
            elif postions[i]>posA and speeds[i]<0:
                rightValidAnts.append(postions[i])
                numRight += 1

        if numLeft == numRight:
            print "Cannot fall!"
        elif numLeft > numRight:
            leftValidAnts.sort()
            print leftValidAnts[numRight]
        else:
            rightValidAnts.sort()
            print rightValidAnts[numLeft]
    except:
        break 

/*
 只需要考虑A左边向右走的和A右边向左走的，数量相同则不会掉下去，
 哪边多则A最终就是朝哪边的方向走（左多向右走），且其轨迹是按照左右抵消后的第一个蚂蚁算
*/
#include <bits/stdc++.h>
using namespace std;
const int AX = 1e2 + 6 ;
struct Node{
	int  p , d ;
	bool operator < ( const Node &x )const{
		return p < x.p ; 
	}
}a[AX] ; 
vector<int>l;
vector<int>r;
int main() {
	int n ;
	while( ~scanf("%d",&n) ) {
		int dir = 0 ;
		l.clear();
		r.clear();
		int x , y ;
		for( int i = 0 ; i < n ; i++ ) {
			scanf("%d%d",&a[i].p,&a[i].d);
		}
		sort( a , a + n );
		for( int i = 0 ; i < n ; i ++ ){
			if( !a[i].d ) { dir = 1 ; continue ;} 
			if( dir == 0 && a[i].d == 1 )  l.push_back(a[i].p);
			if( dir == 1 && a[i].d == -1 ) r.push_back(a[i].p);
		}
		int numl = l.size() ; 
		int numr = r.size() ; 
		sort( l.begin() , l.end() );
		sort( r.begin() , r.end() );
		if( numl == numr ) {
			printf("Cannot fall!\n");
		} else {
			if( numl > numr ) {
				printf("%d\n",100-l[numl-numr-1]);
			} else {
				printf("%d\n",r[numl]);
			}
		}
	}
	return 0 ;
}

这道题其实不需要考虑单个蚂蚁具体如何运动
这样非常复杂
如果从总体上来考虑的话，可以想见
所有蚂蚁速度交换的最终结果类似于速度平移
所有向左运动的蚂蚁平移到左边
所有向右运动的蚂蚁平移到右边
并且其相对位置始终不变
你可以理解为速度的二次按序分配
现在我们只需要知道是哪个蚂蚁的速度被“分配”给了蚂蚁A
考虑在蚂蚁A左边的蚂蚁数
以及向左运动的蚂蚁数
这两个变量的相对大小决定了蚂蚁A的最终运动方向
而蚂蚁A的坠落时间涉及到究竟是哪一个蚂蚁“给了”A速度
这一点可以通过上述两个变量推出来
其中，向左和向右的坠落时间计算有点不同，需要注意

#include<iostream>
using namespace std;
int main(){
    int n;
    cin>>n;
    int p,d;//position, direction
    int ant[101]={0};
    int left=0;//向左蚂蚁数
    int flag=0;//标记A蚂蚁position
    while(cin>>p>>d){
        ant[p]=d;//记录所有蚂蚁的位置与方向
        if(d==-1)
            left++;//记录向左蚂蚁总数
        if(d==0)
            flag=p;
    }
    int aleft=0;//A左侧蚂蚁的数量
    for(p=1;p<flag;p++)
        if(ant[p]!=0)
            aleft++;
    int th=0;//从左向右记录第几个向左/右的蚂蚁
    if(left<aleft){//如果向左蚂蚁数小于A左侧蚂蚁数，则速度交换的最终结果是A向右运动
        for(p=1;;p++){//从左向右寻找第aleft-left个向右运动的蚂蚁
            if(ant[p]==1)
                th++;
            if(th==aleft-left){
                cout<<100-p<<endl;
                break;
            }
        }
    }
    else if(left>aleft){//如果向左蚂蚁数大于A左侧蚂蚁数，则速度交换的最终结果是A向左运动
        for(p=1;;p++){//从左向右寻找第aleft+1个向左运动的蚂蚁
            if(ant[p]==-1)
                th++;
            if(th==aleft+1){
                cout<<p-0<<endl;
                break;
            }
        }
    }
    else//如果向左蚂蚁数等于A左侧蚂蚁数，则速度交换的最终结果是A静止不动
        cout<<"Cannot fall!"<<endl;
    return 0;
}

/*本题最重要的逻辑是蚂蚁的相对位置永远不变！！这个逻辑直接推导出了本题的解法之一
 有参考 http://www.cnblogs.com/liangrx06/p/5083868.html
  不过因为没有注解，所以自己写了一点
首先，我们来确定怎么判断蚂蚁不会坠落，有两种情况————
   第一种：静止的蚂蚁两边的蚂蚁都不会碰到这只蚂蚁，也就是说，左边的往左走，右边的往右走
   第二种：蚂蚁的右边有向左走的，左边有向右走的，按照一般的理解一开始静止的蚂蚁一定
   是会掉下去的，但是注意一开始提到的那个逻辑，蚂蚁的相对位置不变，并且移动方向也不变！
   什么意思呢，比如整个树枝上向左走有n个，向右走有m个。那么在任何时间向左走和向右走的
   数量都是n和m，这时候结合蚂蚁的相对位置，在无限的时刻，向左走的n只蚂蚁都掉下了树枝，
   这n只不一定都是原来初始状态向左走的，但一定是一开始左边的n只蚂蚁，因为相对位置不变。
   同理，右边m只也都掉出去了，那么如果n==m，并且静止的蚂蚁左右都有n(m)只。那么，在某个时刻，
   左边n只无论之前是向哪里走的，一定都下去了。
   所以，我们把结论推广，只要静止的蚂蚁左边的蚂蚁数量，等于所有蚂蚁中往左走的数量，
   亦或者右边的等于向右走的那么它就不会掉下去。
    
那么，怎么判断蚂蚁什么时候下去呢
   这时候肯定能确定这只蚂蚁左右数量不等了。接下来就是很巧妙的思想了，如果该蚂蚁
   左边的蚂蚁数量小于向左走的蚂蚁数量,那么它总会加入向左走的大军最后掉落。这时候
   我们宏观的去看，我们定位所有在向左走的蚂蚁，并且定位静止的那只蚂蚁的位置，并且
   标记为k(第k个蚂蚁)，这时开始移动，我们看不到蚂蚁之间交换速度，我们只知道他们
   像是穿过对方继续往下走。让蚂蚁继续走，直到某一刻我们观察到第k只向左走的蚂蚁
   掉下去了，暂停。现在考虑所有蚂蚁的相对位置不变！如果是第k个向左走的蚂蚁下去了
   那么他之前的向左走的蚂蚁都下去了，反映到相对位置上来说，就是树枝上左边k-1只都下去了，
   那么这一瞬间掉下去的想必就是相对位置在第k的蚂蚁了————也就是原来静止的那只。
   也就是说一开始所有向左走的蚂蚁中，第k个蚂蚁要走多远，就是最终答案！！
   同样，如果反过来，右边的少于向右走的，也一样，
*/

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;

struct Ant
{
    int position;
    int direct;    //方向
    bool operator < (const Ant &a) const
    {
        return position<a.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());
        //////接下来要做的就是找到静止的那只的位置，为此我们要先排序
        //这样找到的静止的蚂蚁左边有几只就出来了
        int target,toLeft = 0;    //这里选用向左走的为基准来做
        for(int i = 0; i<n; i++)    //遍历所有蚂蚁
        {
            if(ant[i].direct == 0)
                target = i;
            if(ant[i].direct == -1)
                toLeft++;
        }//现在的target就是静止的蚂蚁左边的数量了
        bool flag = false;
        int ans;
        if(toLeft == target)
            flag = true;
        else if (toLeft > target)//这样的话我们要找的就是所有向左走的蚂蚁中，第target蚂蚁
        {
            int cnt = 0;//计数器
            for(int i = 0; i<n; i++)
            {
                if(ant[i].direct == -1 && cnt == target)
                {
                    ans = ant[i].position;
                    break;
                }
                else if(ant[i].direct == -1)
                    cnt++;
            }
        }
        else    //向左走的蚂蚁少，那么目标蚂蚁会向右落下
        {
            int cnt = 0;
            for(int i = n - 1; i>=0; i--)
            {
                if(ant[i].direct == 1 && cnt == n - target - 1)//相应的变化，cnt要变成静止蚂蚁右边的蚂蚁数量
                {
                    ans = 100 - ant[i].position;
                    break;
                }
                else if(ant[i].direct == 1)
                    cnt++;
            }
        }
        if(flag)
            printf("Cannot fall!\n");
        else
            printf("%d\n",ans);
    }//while
    return 0;
}//main

#include<bits/stdc++.h>
using namespace std;
struct node{
    int x,y,z;
    node(){x=-1;y=-1;z=-1;}
};//记录某个位置有无向左向右或静止的蚂蚁
int main(){
    int num,p[100],s[100],a,r;
    cin>>num;r=num;
    for(int i=0;i<num;i++){
        cin>>p[i]>>s[i];
        if(s[i]==0)a=i;
    }
    for(int count=0;;count++){
        node n[101];
        if(p[a]==0||p[a]==100){cout<<count<<endl;break;}
        else if(s[a]==0&&r==1){cout<<"Cannot fall!"<<endl;break;}
        for(int i=0;i<num;i++){
            if(s[i]==1)p[i]++,n[p[i]].x=i;
            if(s[i]==-1)p[i]--,n[p[i]].z=i;
            if(s[i]==0)n[p[i]].y=i;
            if((p[i]==0||p[i]==100)&&s[i]!=2)r--,s[i]=2;//置已掉落的蚂蚁速度为2以后不再考虑
        }
        int tmp;
        for(int i=1;i<=99;i++){
            if(i!=99&&n[i+1].x!=-1&&n[i].z!=-1){
                p[n[i+1].x]--;s[n[i+1].x]=-1;p[n[i].z]++;s[n[i].z]=1;tmp=n[i+1].x,n[i+1].x=n[i].z,n[i].z=tmp;
            }//出现交叉则回溯，下面碰撞则交换速度
            if(n[i].x!=-1&&n[i].z!=-1){
                s[n[i].x]=-1;s[n[i].z]=1;
            }
            else if(n[i].x!=-1&&n[i].y!=-1){
                s[n[i].y]=1;s[n[i].x]=0;
            }
            else if(n[i].y!=-1&&n[i].z!=-1){
                s[n[i].y]=-1;s[n[i].z]=0;
            }
        }
    }
    return 0;
}//思路1，直接模拟蚂蚁的位移
//思路2，利用蚂蚁个体无区别的性质，问题等价于一群可以互相穿过的蚂蚁
#include<bits/stdc++.h>
using namespace std;
int main(){
    int num,p[100],s[100],a,l=0,r=0;
    cin>>num;
    for(int i=0;i<num;i++){
        cin>>p[i]>>s[i];
        if(s[i]==1)r++;
        else if(s[i]==0)a=i;
        else l++;
    }
    int apos=0;
    for(int i=0;i<num;i++){
        if(p[i]<p[a])apos++;
    }
    a=apos;//找到静止蚂蚁的位置序号而不是输入id
    if(a==l)cout<<"Cannot fall!"<<endl;
    else{
        int flag=a<l?1:0,cnt=0;
        for(int count=0;;count++){
            if((flag&&cnt==a+1)||(!flag&&cnt==num-a)){cout<<count<<endl;break;}
            for(int i=0;i<num;i++){
                if(s[i]==1)p[i]++;
                if(s[i]==-1)p[i]--;
                if(flag){if(p[i]==0)cnt++;}
                else if(p[i]==100)cnt++;
            }
        }
    }
    return 0;
} 

没用各位大佬们无敌的思想，硬模拟的，老天爷呀
#include<iostream>
#include<algorithm>
#include<stack>
#include<queue>
#include<string.h>
#include<string>
#include<stdio.h>
#include<math.h>
#include<map>
using namespace std; 
struct Ant{
	int loc;
	int con;
	bool operator< (const Ant& r)const
	{
		return loc<r.loc;
	}
};
Ant ant[100];
int main()
{
	int N;
	int q;
	while(scanf("%d",&N)!=EOF)
	{
		for(int i=0;i<N;i++)
		{
			scanf("%d%d",&ant[i].loc,&ant[i].con);
		}
		sort(ant,ant+N);
		for(int i=0;i<N;i++)
		if(!ant[i].con)
		{
			q=i;
			break;
		}
		int time=0;
		int begin=0,end=N-1;  //记录还有几只蚂蚁没走完
		while(1)           
		{
			bool sign=false;
			while(!sign)    //因为可能一堆蚂蚁堆在一起会多次交换速度，通过while模拟
			{
				sign=true;   //在一次循环中没有交换，则证明大家都可以走不会相遇了
				for(int i=begin;i<end;i++)
				{
					int a=ant[i].loc+ant[i].con;
					int b=ant[i+1].loc+ant[i+1].con;
					if(a>b)  
					{
						swap(ant[i].con,ant[i+1].con);
						if(ant[i].con&&ant[i+1].con&&ant[i].loc!=ant[i+1].loc) 
						{ //如果两只蚂蚁一只往左走一只向右走，则他们在本次均会回到自己的位置上
							ant[i].loc++;
							ant[i+1].loc--;
						}
						sign=false;
					}
				}
			}
			for(int i=begin;i<=end;i++)
			{
				ant[i].loc+=ant[i].con;    //蚂蚁根据自己的方式行走
				if(!ant[i].loc) begin++;
				else if(ant[i].loc==100) end--;
			}
			time++;	
			if(!ant[q].loc||ant[q].loc==100)
			{
				printf("%d\n",time);
				break;
			}
			if(begin==q&&end==q&&!ant[q].con) //没有其他蚂蚁而且这只蚂蚁还不走了 
			{
				printf("Cannot fall!\n");
				break;
			}
			
		}
	}
 } 

/*
提供一种暴力模拟的思路：
1.每只蚂蚁行动一次，不管是否遇到别的蚂蚁。
2.如果有距离相差1，且相互靠近的蚂蚁，这两只蚂蚁速度取反，回退一格。
3.遍历木棒上每一个位置，两只蚂蚁位置相同，速度交换；三只蚂蚁位置相同，速度分别取反。
*/

#include <iostream>
#include <vector>

using std::cin;
using std::cout;
using std::endl;
using std::vector;

struct ant{
    int position;
    int speed;
};

int main (){
    int n;
    while(cin >> n){
    int zero = 0;
    vector<ant> vec, vec_temp;
    for(int i = 0; i < n; i++){
        int a, b;
        cin >> a;
        cin >> b;
        if(b == 0){
            zero = i;
        }
        ant _ant = {a, b};
        vec.push_back(_ant);
    }

    int u;
    int pos, spe;
    ant temp_ant;
    for(u = 1; u < 200; u++){

        for(auto &elem_1 : vec){ //每只蚂蚁行动一次，不管是否遇到别的蚂蚁
            elem_1.position = elem_1.position + elem_1.speed;
        }

        for(int i = 0; i < vec.size(); i++){ //如果有距离相差1，且相互靠近的蚂蚁，这两只蚂蚁速度取反，回退一格
            for(int j = i + 1; j < vec.size(); j++){
                if((vec[i].position - vec[i].speed == vec[j].position) && (vec[i].speed == (-1) * vec[j].speed)){
                    vec[j].position = vec[j].position - vec[j].speed;
                    vec[i].position = vec[i].position - vec[i].speed;
                    vec[i].speed = vec[i].speed * -1;
                    vec[j].speed = vec[j].speed * -1;
                }
            }
        }

        for (int k = 0; k <= 100; k++){
            int ant_1 = -1, ant_2 = -1, ant_3 = -1;
            for (int i = 0; i < vec.size(); i++){
                if (vec[i].position == k){
                    if(ant_1 < 0){//记录在同一点上的蚂蚁，最多3只蚂蚁同时在一个点上
                        ant_1 = i;
                    }
                    else if(ant_2 < 0){
                        ant_2 = i;
                    }
                    else if(ant_3 < 0){
                        ant_3 = i;
                    }
                }
            }
            if ((ant_2 >= 0)&&(ant_3 < 0)){//两只蚂蚁位置相同，速度交换
                int temp = vec[ant_1].speed;
                vec[ant_1].speed = vec[ant_2].speed;
                vec[ant_2].speed = temp;
            }
            else if(ant_3 > 0){ //三只蚂蚁位置相同，速度取反
                vec[ant_1].speed = (-1) * vec[ant_1].speed;
                vec[ant_2].speed = (-1) * vec[ant_2].speed;
                vec[ant_3].speed = (-1) * vec[ant_3].speed;
            }
        }

        //测试用
        //cout <<endl;
        //for(auto &elem_1 : vec){
        //    cout << elem_1.position << "   " <<  elem_1.speed << endl;
        //}
        //cout << "zero = " << zero << endl;;
        //cout <<endl;

        if((vec[zero].position <= 0)||(vec[zero].position) >= 100){ //掉落检测
            cout << u <<endl;
            break;
        }
    }
    if (u == 200){
        cout << "Cannot fall!" << endl;
    }
}
    return 0;
}

//学习了评论区大佬的思路,天真的我竟然还想模拟每个时刻蚂蚁的状态变化
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Ant{
    int pos;
    int dir;
};

bool cmp(Ant lhs, Ant rhs){
    return lhs.pos < rhs.pos;
}

int main(){
    int n;
    cin >> n;
    Ant ant[n];
    vector<Ant> vecl, vecr;
    for(int i=0; i<n; ++i){
        cin >> ant[i].pos >> ant[i].dir;
    }
    sort(ant, ant+n, cmp);
    int A;
    for(int i=0; i<n; ++i){     //找分割点
        if(ant[i].dir == 0) A=i;
    }
    for(int i=0; i<A; ++i){     //统计左边往右走的蚂蚁
        if(ant[i].dir == 1) {
            vecl.push_back(ant[i]);
        }
    }
    for(int i=A; i<n; ++i){     //统计右边往左走的蚂蚁
        if(ant[i].dir == -1) {
            vecr.push_back(ant[i]);
        }
    }
    int left = vecl.size(), right = vecr.size();    //比较数量
    if(left>right){
        cout << 100-vecl[left - right -1].pos << endl;
    } else if(left<right){
        cout << vecr[left].pos << endl;
    }else{
        cout << "Cannot fall!" << endl;
    }
}

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
bool emp(int a, int b){
    return a>b;
}
bool emp1(vector<int> a, vector<int> b){
    return a[0]<b[0];
}
int main() {
    int n,index=-1,a,b;
    cin>>n;
    vector<vector<int>> v(n,vector<int>(2));
    for(int i = 0 ;i<n;i++){
        cin>>v[i][0]>>v[i][1];
        if(v[i][1]==0){
            index = v[i][0];
        }
    }
    sort(v.begin(),v.end(),emp1);
    vector<int> l,r;
    for(int i = 0;i<n;i++){
        if(v[i][0]<index){
            if(v[i][1]>0) l.push_back(v[i][0]);
        }
        if(v[i][0]>index){
            if(v[i][1]<0) r.push_back(v[i][0]);
        }
    }
    sort(l.begin(),l.end(),emp);
    int ln = l.size(),rn = r.size();
    if(ln==rn) cout<<"Cannot fall!"<<endl;
    else{
        if(ln>rn) cout<<100-l[rn]<<endl;
        else cout<<r[ln]<<endl;
    }
}
// 64 位输出请用 printf("%lld")

#include <algorithm>
#include <iostream>
#include <cstdio>
using namespace std;

struct ant{
    int dist;
    int direct;
    bool operator<(const ant& a) const{
        return dist<a.dist;
    }
};
ant ants[100];

int main(){
    int n;
    while(scanf("%d",&n)!=-1){
        for(int i=0;i<n;i++){
            scanf("%d%d",&ants[i].dist,&ants[i].direct);
        }
        sort(ants,ants+n);

        //找到目标蚂蚁
        int tag;
        for(int i=0;i<n;i++){
            if(ants[i].direct==0){
                tag=i;
            }
        }
        bool find=false;
        //假设往左掉，那么必然会有tag+1个蚂蚁的方向向左，且从左开始数第tag+1向左的蚂蚁所用时间即为所求
        for(int i=0,flag=0;i<n;i++){
            if(ants[i].direct==-1){
                ++flag;
                if(flag==tag+1){
                    printf("%d\n",ants[i].dist);
                    find=true;
                    break;
                }
            }
        }
        if(find){
            continue;
        }
        //假设往右掉，那么必然会有n-tag个蚂蚁的方向向右，且从右开始数第n-tag向右的蚂蚁所用时间即为所求
        for(int i=n-1,flag=0;i>=0;i--){
            if(ants[i].direct==1){
                ++flag;
                if(flag==n-tag){
                    printf("%d\n",100-ants[i].dist);
                    find=true;
                    break;
                }
            }
        }
        if(find){
            continue;
        }
        //往左往右都没找到，说明掉不下去
        printf("Cannot fall!\n");
    }
    return 0;
}