//拿到题目应该先考虑蚂蚁A为什么不会坠落 //蚂蚁移动过程中,向左移动的蚂蚁数量保持不变,向右移动的蚂蚁数量不变; //不坠落的情况有两种,即A两边的蚂蚁,右边的蚂蚁向右边走,左边的蚂蚁向左边走,则这一类的蚂蚁都不会与A相撞; //另一种情况就是存在右边的蚂蚁向左边走,左边的蚂蚁向右边走,但是,这两种蚂蚁的数量是相等的,这样也不会坠落。 /* //这种方法我怎么都想不明白 #include <iostream> #include <cstdio> #include <algorithm> using namespace std; struct ant_t{ int pos; int rate; }; bool cmp(ant_t a, ant_t b) { return a.pos < b.pos; } int main() { int i, N; ant_t ant[100]; int moveL, moveR, left, right;//moveL/moveR表示最初方向向左(右)移动的蚂蚁数量 //left/right表示最初静止的蚂蚁左边/右边蚂蚁数量 while (scanf("%d", &N) != EOF) { moveL = moveR = 0; for (i = 0; i < N; i++) { scanf("%d %d", &ant[i].pos, &ant[i].rate); if (ant[i].rate == -1) { moveL++; } else if (ant[i].rate == 1) { moveR++; } } sort(ant, ant + N, cmp); left = 0; for (i = 0; i < N; i++) { if (ant[i].rate == 0) { break; } left++; } right = N - left - 1; int leftFall = 0, rightFall = 0, t = 0; if (left == moveL || right == moveR) { printf("Cannot fall!\n"); } else if (left < moveL || right > moveR) {//中间的蚂蚁最终会从左边掉下树枝//它的这个判断我怎么都想不通 while (1) { for (int j = 0; j < N; j++) { if (ant[j].pos == 0) { leftFall++; } ant[j].pos += ant[j].rate; } if (leftFall == left + 1) { printf("%d\n", t); break; } t++; } } else if (left > moveL || right < moveR) {//中间的蚂蚁最终会从右边掉下数值 while (1) { for (int j = 0; j < N; j++) { if (ant[j].pos == 100) { rightFall++; } ant[j].pos += ant[j].rate; } if (rightFall == right + 1) { printf("%d\n", t); break; } t++; } } } return 0; } */ #include <algorithm> #include <iostream> using namespace std; struct Ant { int pos; int speed; }; bool cmpl (Ant x,Ant y) { return x.pos>y.pos; } bool cmpr (Ant x,Ant y) { return x.pos<y.pos; } int main() { int n; while(cin>>n) { Ant left[100]; Ant right[100]; Ant a[100];//初始全部蚂蚁的状态 int Apos;//A的位置 int i=0;//A右边的蚂蚁 ,并且向左行动 的数量 int j=0;//A左边的蚂蚁 ,并且向右行动 的数量 for(int k=1;k<=n;k++) { cin>>a[k].pos>>a[k].speed; if(a[k].speed==0)Apos=a[k].pos; } for(int k=1;k<=n;k++) { if(a[k].pos<Apos && a[k].speed>0)//蚂蚁在A的左边,向右行动 { j++; left[j].pos=a[k].pos; left[j].speed=a[k].speed; } else if(a[k].pos>Apos && a[k].speed<0)//蚂蚁在A的右边,向左行动 { i++; right[i].pos=a[k].pos; right[i].speed=a[k].speed; } } sort(left+1,left+j+1,cmpl); sort(right+1,right+i+1,cmpr); if(i==j || (j==0 && i==0)) { cout<<"Cannot fall!"<<endl; } else if(j>i) { cout<<(Apos-left[i+1].pos)+(100-Apos)<<endl; } else if(j<i) { cout<<right[j+1].pos<<endl; } } return 0; } /*用了向量的正确解法 #include <iostream> #include <cstdio> #include <vector> #include <algorithm> using namespace std; const int MAXN = 100 + 10; struct Ant { int position; int direction; }; bool Compare(Ant x, Ant y) { return x.position < y.position; } Ant ants[MAXN]; int main() { int n ; while(scanf("%d",&n) != EOF) { vector<int> left; vector<int> right; int position; for (int i = 0; i < n; ++i) { scanf("%d%d", &ants[i].position, &ants[i].direction); if (ants[i].direction == 0) { //确定A的位置 position = ants[i].position; } } sort(ants, ants + n, Compare); for (int i = 0; i < n; ++i) { //只找出那些会与A相撞的 if (ants[i].position < position && ants[i].direction == 1) { left.push_back(ants[i].position); } if (ants[i].position > position && ants[i].direction == -1) { right.push_back(ants[i].position); } } if (left.size() == right.size()) { //左右数量相等,则不会坠落 printf("Cannot fall!\n"); } else if (left.size() < right.size()) { //右边数量大于左边,则会向左边坠落,时间为两边数量消完之后 //的右边第一个的位置与0之间的距离 printf("%d\n", right[left.size()]); } else { //左边数量大于右边,则会向右边坠落,时间为两边数量消完之后 //的左边最后一个的位置与100之间的距离,因为左边的元素是从左往右 //排列,但是相消的时候,左边元素是从后往前消去 printf("%d\n", 100 - left[left.size() - right.size() - 1]); } } return 0 ; } */