[编程题]坠落的蚂蚁
- 热度指数：10573 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
- 算法知识视频讲解
一根长度为1米的木棒上有若干只蚂蚁在爬动。它们的速度为每秒一厘米或静止不动，方向只有两种，向左或者向右。如果两只蚂蚁碰头，则它们立即交换速度并继续爬动。三只蚂蚁碰头，则两边的蚂蚁交换速度，中间的蚂蚁仍然静止。如果它们爬到了木棒的边缘（0或100厘米处）则会从木棒上坠落下去。在某一时刻蚂蚁的位置各不相同且均在整数厘米处（即1，2，3，…99厘米），有且只有一只蚂蚁A速度为0，其他蚂蚁均在向左或向右爬动。给出该时刻木棒上的所有蚂蚁位置和初始速度，找出蚂蚁A从此时刻到坠落所需要的时间。
输入描述:
第一行包含一个整数表示蚂蚁的个数N（2<=N<=99），之后共有N行，每一行描述一只蚂蚁的初始状态。每个初始状态由两个整数组成，中间用空格隔开，第一个数字表示初始位置厘米数P（1<=P<=99），第二个数字表示初始方向,-1表示向左，1表示向右，0表示静止。
输出描述:
蚂蚁A从开始到坠落的时间。若不会坠落，输出“Cannot fall!”
示例1
输入
4 10 1 90 0 95 -1 98 -1
输出
98
#!/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
发表于 2016-05-16 09:03:21
回复(2)
这道题其实不需要考虑单个蚂蚁具体如何运动
这样非常复杂
如果从总体上来考虑的话，可以想见
所有蚂蚁速度交换的最终结果类似于速度平移
所有向左运动的蚂蚁平移到左边
所有向右运动的蚂蚁平移到右边
并且其相对位置始终不变
你可以理解为速度的二次按序分配
现在我们只需要知道是哪个蚂蚁的速度被“分配”给了蚂蚁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;
}
发表于 2020-02-03 00:02:32
回复(1)
/*本题最重要的逻辑是蚂蚁的相对位置永远不变！！这个逻辑直接推导出了本题的解法之一
有参考 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
发表于 2018-03-04 17:16:44
回复(9)
首先，除了蚂蚁A之外，其余蚂蚁碰头交换速度等价于这两只蚂蚁按照原速度继续爬行。
将蚂蚁A想象为红点，其余蚂蚁为黑点，两个黑点相撞互换速度（实际上速度相同，互换的是方向），从视觉上来看，这两个黑点并没有改变状态，而是穿过彼此继续前行。
因此，只需要考虑黑点与红点相撞的情况即可。红点左边向左运动的点永远不会与红点相撞，同理右边向右运动的点亦然。因此只需考虑红点左边向右运动的点数left和红点右边向左运动的点right数。
若left=right，则两边与红点交换的速度相互抵消，红点不会坠落。
若left>right，则红点将与第left-right个点交换速度并最终向右坠落，坠落时间是第left-right个点运动到100的时间。
若left<right，红点最终向左坠落，坠落时间是right与left抵消之后右边第一个right点运动到0的时间。
#include<iostream>
(720)#include<cstdio>
#include<algorithm>
using namespace std;
struct Ant{
int pos; //蚂蚁位置
int dir; //蚂蚁运动方向
bool operator< (const Ant& a)const
{
return pos<a.pos; //规定按pos进行排序
}
};
int main(){
int n,apos,left=0,right=0;
scanf("%d",&n);
Ant ants[n];
for(int i=0;i<n;i++){
scanf("%d%d",&ants[i].pos,&ants[i].dir);
if(ants[i].dir==0) apos=ants[i].pos; //记录蚂蚁A的位置
}
sort(ants,ants+n); //将输入按位置从左到右排序
for(int i=0;i<n;i++){
if(ants[i].pos<apos&&ants[i].dir==1)
left++; //蚂蚁A左边向右走的蚂蚁数
if(ants[i].pos>apos&&ants[i].dir==-1)
right++; //蚂蚁A右边向左走的蚂蚁数
}
if(left==right){
printf("Cannot fall!");
return 0;
}
else if(left>right){
int k=0;
for(int i=0;i<n;i++){
if(ants[i].dir==1) k++;
if(k==left-right){
printf("%d",100-ants[i].pos);
return 0;
}
}
}
else{
int k=0;
for(int i=n-1;i>=0;i--){
if(ants[i].dir==-1) k++;
if(k==right-left){
printf("%d",ants[i].pos);
return 0;
}
}
}
}
发表于 2020-04-16 14:31:13
回复(1)
各位大佬都解释得很好。在下按照自己的思路重新整理了一遍：
除去A以外的所有蚂蚁记为B。B是一个整体。于是可以认为B中的蚂蚁相遇时不会交换速度。
B中的蚂蚁与A相遇时，仍然会交换速度。将B分为四类：A左侧向左走的记为LL，A左侧向右走的蚂蚁记为LR。同样的，规定RR和RL。
显然LL和RR永远不会与A相遇。对A有影响的只有LR和RL。
于是进一步的，情况简化为：A的左边只有向右走的蚂蚁LR，A的右边只有向左走的蚂蚁RL。
经过两次碰撞，A的速度就会被抵消，变为0. 因此，
① 若LR和RL的数目相同，则A最终会静止在木棍上；
② 若LR和RL数目不同，则无法全部相抵消。不妨设LR多一些，那么LR中就有那么一只蚂蚁C，它的右边的LR的同伴都被抵消掉了，C撞到了A，A获得C的速度向右运动，直到坠落。这个过程的时间等同于从C的初始位置向右走到尽头所需要的时间。
代码如下：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct ant { int pos; int dir; };
int main() {
int n;
while (cin >> n && n) {
vector<ant> ants(n);
int a_pos = 0, n_lr = 0, n_rl = 0;
for (int i = n; i--;) { // 输入的同时记录A的位置。
cin >> ants[i].pos >> ants[i].dir;
if (ants[i].dir == 0) a_pos = ants[i].pos;
}
for (int i = ants.size() - 1; i >= 0; i--) { // 数一下LR和RL的个数，同时删除LL和RR。
if ((ants[i].pos - a_pos) * ants[i].dir > 0)
ants.erase(i + ants.begin());
else if (ants[i].pos < a_pos)
n_lr++;
else if (ants[i].pos > a_pos)
n_rl++;
}
// 按位置排序
sort(ants.begin(), ants.end(), [](ant& a, ant& b) {return a.pos < b.pos; });
// 如果左右相抵，则A不会坠落。否则，计算C的位置，得到结果。
if (n_lr == n_rl) {
printf("Cannot fall!\n");
continue;
}
int index = n_lr > n_rl ? (n_lr - n_rl - 1) : (ants.size() - n_rl + n_lr);
printf("%d\n", n_lr > n_rl ? 100 - ants[index].pos : ants[index].pos);
}
return 0;
}
发表于 2020-01-04 21:20:14
回复(7)
总算模拟出来了，虽然大神的解答才是王道，不过，模拟出来可以看一下小蚂蚁们怎么掉下去的。；）
/* simulate dropAnts
*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct ant {
int pos; //0-100
int dir; //-1, 0, 1
bool flag; //indicate ant A
bool operator < (const ant &A) const {
return pos < A.pos;
}
};
vector<ant> vec;
void dump()
{
for (auto c : vec)
cout << "(" << ((c.flag) ? "*": "") << c.pos << "," << c.dir <<") ";
cout << endl;
}
void move()
{
/* move */
for (auto &a : vec) {
if (a.dir == -1)
a.pos -= 1;
else if (a.dir == 1)
a.pos += 1;
}
/* 3 ants meet */
for (int i = 0; i < (int)(vec.size()-2); i += 3) {
if (vec[i].pos == vec[i+1].pos && vec[i+1].pos == vec[i+2].pos)
swap(vec[i].dir, vec[i+2].dir);
}
/* 2 ants meet */
for (int i = 0; i < (int)(vec.size()-1); i++) {
if (vec[i].pos > vec[i+1].pos) {
swap(vec[i].flag, vec[i+1].flag);
swap(vec[i], vec[i+1]);
}
}
/* drop */
for (auto it = vec.begin(); it != vec.end(); ) {
if (it->pos <= 0 || it->pos >= 100)
it = vec.erase(it);
else
++it;
}
}
bool isDrop()
{
for (auto c : vec)
if (c.flag)
return false;
return true;
}
int main()
{
int n;
while (cin >> n) {
vec.clear();
for (int i = 0; i < n; ++i) {
ant a;
a.flag = false;
cin >> a.pos >> a.dir;
if (a.dir == 0)
a.flag = true;
vec.push_back(a);
}
sort(vec.begin(), vec.end());
int cnt = 0;
while (!isDrop()) {
if (vec.size() == 1 && vec[0].dir == 0)
break;
//dump();
move();
++cnt;
}
if (isDrop())
cout << cnt << endl;
else
cout << "Cannot fall!" << endl;
}
return 0;
}
发表于 2019-02-13 12:50:18
回复(3)
#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;
}
编辑于 2020-03-17 21:25:22
回复(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;
}
}
}
}
发表于 2020-01-30 17:09:12
回复(0)
/*
提供一种暴力模拟的思路：
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;
}
发表于 2022-01-19 14:52:31
回复(0)
强行模拟。。。
// E2-11 坠落的蚂蚁
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class mayi
{
public:
int pos;
int speed;
int flag = 0; //初始静止蚂蚁A
mayi() {
pos = 0;
speed = 0;
}
mayi(int p, int s) {
pos = p;
speed = s;
}
void Flag() {
flag = 1;
}
bool IsFlag() {
return flag;
}
bool NotEdge() {
return pos != 0 && pos != 100;
}
void move() {
pos += speed;
}
bool operator==(const mayi& b) {
return pos == b.pos;
}
bool operator<(const mayi& b) {
if (pos < b.pos) {
return true;
}
else if (pos == b.pos) {
return speed > b.speed;
}
else {
return false;
}
}
void Print() {
cout << '[' << pos << ',' << speed << ',' << flag << ']' << endl;
}
private:
};
bool cmp(mayi a, mayi b) {
return a < b;
}
bool SpecialEncounter(mayi a,mayi b) {
if (a.speed > 0 && b.speed < 0 && a.pos - b.pos == 1) {
return true;
}
else if (a.speed < 0 && b.speed > 0 && a.pos - b.pos == -1) {
return true;
}
else {
return false;
}
}
void swapspeed(mayi &a, mayi &b) {
int tempv = a.speed;
a.speed = b.speed;
b.speed = tempv;
}
int main()
{
int n;
while (cin >> n) {
vector<mayi> mayis;
int A; //初始静止蚂蚁A序号
for (int i = 0; i < n; i++) {
int v, p;
cin >> p >> v;
mayi mayi(p, v);
if (v == 0) {
mayi.Flag();
A = i;
}
mayis.push_back(mayi);
}
//for (int i = 0; i < n; i++) {
// mayis[i].Print();
//}
int time = 0;
int notfall = 0;
while (mayis[A].NotEdge()) {
for (int i = 0; i < n; i++) {
mayis[i].move();
}
time++;
sort(mayis.begin(), mayis.end(), cmp);
for (int i = 0; i < n; i++) {
if (mayis[i].IsFlag()) {
A = i;
}
if (mayis[i].NotEdge() == false) {
mayis[i].speed = 0;
}
}
if (A < n - 1 && SpecialEncounter(mayis[A], mayis[A + 1])){
mayis[A].flag = 0;
mayis[A + 1].Flag();
A = A + 1;
}
else if (A > 0 && SpecialEncounter(mayis[A], mayis[A - 1])) {
mayis[A].flag = 0;
mayis[A - 1].Flag();
A = A - 1;
}
for (int i = 0; i < n - 1; i++) {
if (mayis[i] == mayis[i + 1]) {
if (i + 2 < n) {
if (mayis[i] == mayis[i + 2]) {
swapspeed(mayis[i], mayis[i + 2]);
i += 2;
}
else {
swapspeed(mayis[i], mayis[i + 1]);
i++;
}
}
else {
swapspeed(mayis[i], mayis[i + 1]);
i++;
}
}
}
bool allzero = true;
for (int i = 0; i < n; i++) {
if (mayis[i].speed != 0) {
allzero = false;
}
}
notfall = allzero && mayis[A].NotEdge();
if (notfall) {
break;
}
}
if (notfall) {
cout << "Cannot fall!" << endl;
}
else {
cout << time << endl;
}
}
}
编辑于 2024-01-12 17:27:45
回复(0)
1、非蚂蚁A的其余蚂蚁相碰，相当于互相穿过对方。
2、初始在A左侧往左走的蚂蚁和初始在A右侧往右走的蚂蚁对A的计算没有影响。
以初始在A左侧向左走的蚂蚁X为例：
对于所有向左走的蚂蚁Y（不论是否是A），因为速度一样，相对静止，所以不会相遇；
对于所有向右走的蚂蚁Y，Y不可能是A，否则X本就该在A的右侧。若相碰等于穿过对方，所以对整体蚂蚁没有影响。
3、取决于A坠不坠落的因素在于初始在A右侧往左走的蚂蚁R和初始在A左侧往右走的蚂蚁L。
若R的数量多于L，那么最终A从0处掉落，掉落时间等于R里面最靠近A位置的第L+1只蚂蚁。
若R的数量少于L，那么最终A从100处掉落，掉落时间等于L里面最靠近A位置的从右往左数第R+1只蚂蚁。
若R的数量等于L，那么最终A永远不会掉落，会停留在初始位置。
4、初始位置总会有一只静止的蚂蚁。初始开始为A，要么一只蚂蚁碰到A代替A留在原地，要么两只蚂蚁同时碰到A，A停留在原地。
上述结论可以画图模拟得出。
#include <bits/stdc++.h>
using namespace std;
vector<int> RtoL; //记录初始在A右侧向左走的蚂蚁位置
vector<int> LtoR; //记录初始在A左侧向右走的蚂蚁位置
int place, dir;
int N, A;
vector<pair<int, int>> ants;
int main()
{
cin >> N;
for (int i = 1; i <= N; i++)
{
cin >> place >> dir;
if (dir == 0) //得到A的位置
A = place;
else //记录其余蚂蚁位置
ants.emplace_back(make_pair(place, dir));
}
for (int i = 0; i < ants.size(); i++)
{
if (ants[i].second == -1 && ants[i].first > A) //右侧往左走的
RtoL.emplace_back(ants[i].first);
else if (ants[i].second == 1 && ants[i].first < A) //左侧往右边走的
LtoR.emplace_back(ants[i].first);
}
if (RtoL.size() == LtoR.size()) //两侧蚂蚁数量相等
cout << "Cannot fall!" << endl;
else
{
if (RtoL.size() > LtoR.size()) //右侧多于左侧
{ //右侧第一只多于左侧数量的蚂蚁位置走到最左侧就是所用时间
sort(RtoL.begin(), RtoL.end());
cout << RtoL[LtoR.size()] << endl;
}
else //左侧多于右侧
{ //左侧第一只（从A往左数）多于右侧数量的蚂蚁位置走到最右侧的时间就是所用时间
sort(LtoR.begin(), LtoR.end(), greater<int>());
cout << 100 - LtoR[RtoL.size()] << endl;
}
}
return 0;
}
发表于 2022-07-20 21:37:21
回复(0)
/*
只需要考虑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 ;
}
发表于 2020-03-12 12:35:07
回复(0)
思路：蚂蚁只是在传递运动状态。每个运动状态在不同的时刻可能存在于不同的蚂蚁，但运动状态还是按照自己的方位和速度继续前进。只需要考虑蚂蚁A继承了谁的运动状态
发表于 2025-03-17 20:09:16
回复(0)
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//蚂蚁在木棍上移动的时候，互相交换速度，但相对位置没有变化
//因为一旦碰头就要往回走，不会出现相对位置穿越的情况
//另外，整体上看，即使有速度交换，但是宏观上向左和向右的数量不变
//这是因为速度交换有两种情况：1、静止和有速度的->有速度和静止的 2、两个相反方向的->两个相反方向的
//这样我们就有了两个重要的条件，宏观上看整体的移动，在任意时刻：1、相对位置不变 2、向左和向右的数量不变
//由于相对位置不变，向左走的速度最终只能传导到左边
//假设共有ln个向左走的蚂蚁，最后从左侧数ln个蚂蚁成为了向左走的蚂蚁
//在相当一段时间内，这ln个蚂蚁会从左边掉下去
//右侧的蚂蚁同理，rn个蚂蚁会从右边掉下去
//所以现在我们有了一个结论：掉下去的蚂蚁要么是左边ln个要么是右边rn个
//只有A在这两个范围内才会掉下去
//解决了A是否会掉下去的问题，现在来考虑A在什么时刻掉下去
//假设A最终会从左边掉下去，那么她一定在ln范围内
//现在假设第一个向左走的蚂蚁向左传导速度，只有当向左的状态传递到最左侧的时候最左侧的蚂蚁才到最终状态。否则右侧还会和最左侧的蚂蚁碰撞
//所以假设A是左侧第k个蚂蚁，她只能等待第k个向左走的蚂蚁将状态传递给她
//而状态传递的过程，宏观来看就是一直向左走，速度没有停滞
//所以相当于A需要第k个向左走的蚂蚁，从初始走到端点的时间才会掉下去
//算法需要计算A是不是在向左（右）走的数量范围内，找到第k个向左（右）走的蚂蚁
int main(){
//先判断A是否能掉下去
int n;
int left_n=0;//向左走的数量
int right_n=0;//向右走的数量
int pos,dir;
int A_pos;//A的位置
int a_l=1;//A在左边第几个
int a_r=1;//A在右边第几个
vector<int> left_ants;//向左的蚂蚁初始位置
vector<int> right_ants;//向右的蚂蚁初始位置
scanf("%d",&n);
for(int i=0;i<n;++i){
scanf("%d %d",&pos,&dir);
if(dir==1){
right_ants.push_back(pos);
++right_n;
}
else if(dir==-1){
left_ants.push_back(pos);
++left_n;
}
else{
A_pos=pos;
}
}
sort(left_ants.begin(),left_ants.end());
sort(right_ants.rbegin(),right_ants.rend());
for(int i=0;i<left_ants.size();++i){
if(left_ants[i]<A_pos){
++a_l;
}
else{
++a_r;
}
}
for(int i=0;i<right_ants.size();++i){
if(right_ants[i]<A_pos){
++a_l;
}
else{
++a_r;
}
}
if(left_n>=a_l){
//向左走的数量大于a在左侧的位置
printf("%d",left_ants[a_l-1]);
}
else if(right_n>=a_r){
printf("%d",100-right_ants[a_r-1]);
}
else if(left_n<a_l&&right_n<a_r){
printf("Cannot fall!");
}
return 0;
}
发表于 2024-03-17 17:38:16
回复(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;
}
}
编辑于 2024-03-12 15:14:19
回复(0)
#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")
发表于 2023-03-27 16:13:57
回复(1)
#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;
}
发表于 2023-03-18 14:23:48
回复(0)
//自己模拟了两小时也没出来，看了高赞的题解才明白思维上的不足，也佩服那些模拟出来的人，真的细致
#include "stdio.h"
#include "algorithm"
using namespace std;
struct ant{
int pos;
int direction;//1为向右，0为静止，-1为向左
};
bool cmp(ant lhs,ant rhs){
if (lhs.pos < rhs.pos)
return true;
else
return false;
}
int main(){
int n;ant array[100];
ant left[100],right[100];
int A;int left_count = 0,right_count = 0;
scanf("%d",&n);
for (int i = 1; i <= n; ++i) {
scanf("%d%d",&array[i].pos,&array[i].direction);
}
sort(array+1,array+n+1,cmp);
for (int i = 1; i <= n; ++i) {
if (array[i].direction == 0){
A = i;
break;
}
}
for (int i = A-1,j = 1; i > 0; --i) {
if(array[i].direction == 1){
left[j].direction = 1;
left[j++].pos = array[i].pos;
++left_count;
}
}
for (int i = A+1,k = 1; i <= n; ++i) {
if(array[i].direction == -1){
right[k].direction = -1;
right[k++].pos = array[i].pos;
++right_count;
}
}
if(left_count == right_count){
printf("Cannot fall!");
} else{
if(left_count > right_count)
printf("%d",100-left[right_count+1].pos);
if(left_count < right_count)
printf("%d",right[left_count+1]);
}
}
发表于 2023-03-13 15:06:22
回复(0)
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
int main(){
int a[100];//最多100只蚂蚁
int n;//蚂蚁个数
int s;//记录静止蚂蚁A的位置
while(cin>>n){
for(int i=0;i<100;i++){
a[i]=3;//随便给一个不是0，1，-1的数就可以
}
int pos,v;
for(int i=0;i<n;i++){
cin>>pos>>v;
a[pos]=v;
if(v==0) s=pos;//唯一的静止蚂蚁A的位置
}
int left=s;//A左边的最近影响蚂蚁（v=+1）
int right=s;//A右边的最近影响蚂蚁（v=-1）
//int res=0;//A移动距离（本题速度为1，移动距离就是移动时间）
while(left>=0&&right<=100){//左边或者右边还有最近蚂蚁（两边没有一边到木棒端点）
while(a[left]!=+1){
left--;
if(left==-1) break;
}
while(a[right]!=-1){
right++;
if(right==101) break;
}
if(left!=-1&&right!=101){
//cout<<"left:"<<left<<",right:"<<right<<endl;
left--;
right++;
}
}
//cout<<"left:"<<left<<",right:"<<right<<endl;
if(left==-1&&right==101){
cout<<"Cannot fall!"<<endl;//不会坠落，说明左右两边为偶数个影响蚂蚁
}
else if(left!=-1){
//res=100-left;
cout<<100-left<<endl;
}
else if(right!=101){
//res=right;
cout<<right<<endl;
}
else{
cout<<"method error!"<<endl;//理论上不会出现这种情况
}
}
return 0;
}
#include <cstdio>
#include <vector>
using namespace std;
int main(){
int a[100];//最多100只蚂蚁
int n;//蚂蚁个数
int s;//记录静止蚂蚁A的位置
while(cin>>n){
for(int i=0;i<100;i++){
a[i]=3;//随便给一个不是0，1，-1的数就可以
}
int pos,v;
for(int i=0;i<n;i++){
cin>>pos>>v;
a[pos]=v;
if(v==0) s=pos;//唯一的静止蚂蚁A的位置
}
int left=s;//A左边的最近影响蚂蚁（v=+1）
int right=s;//A右边的最近影响蚂蚁（v=-1）
//int res=0;//A移动距离（本题速度为1，移动距离就是移动时间）
while(left>=0&&right<=100){//左边或者右边还有最近蚂蚁（两边没有一边到木棒端点）
while(a[left]!=+1){
left--;
if(left==-1) break;
}
while(a[right]!=-1){
right++;
if(right==101) break;
}
if(left!=-1&&right!=101){
//cout<<"left:"<<left<<",right:"<<right<<endl;
left--;
right++;
}
}
//cout<<"left:"<<left<<",right:"<<right<<endl;
if(left==-1&&right==101){
cout<<"Cannot fall!"<<endl;//不会坠落，说明左右两边为偶数个影响蚂蚁
}
else if(left!=-1){
//res=100-left;
cout<<100-left<<endl;
}
else if(right!=101){
//res=right;
cout<<right<<endl;
}
else{
cout<<"method error!"<<endl;//理论上不会出现这种情况
}
}
return 0;
}
发表于 2022-07-28 20:55:09
回复(0)
问题信息
难度：
40条回答
337收藏
10259浏览
通过挑战的用户
查看代码-
2023-03-05 20:17:26
-
2023-02-14 00:06:44
-
2023-02-07 16:26:42 -
2023-01-16 11:38:16 -
2023-01-11 10:35:18
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
