<--
如果对你有帮助的话点个赞呗
<--
不喜欢的话请点个踩,并在评论区告诉我哪里需要改正!
坠落的蚂蚁题解
题目描述
一根长度为 $1$ 米的木棒上有若干只蚂蚁在爬动。
它们的速度为每秒一厘米或静止不动,方向只有两种,向左或者向右。
如果两只蚂蚁碰头,则它们立即交换速度并继续爬动。
三只蚂蚁碰头,则两边的蚂蚁交换速度,中间的蚂蚁仍然静止。
如果它们爬到了木棒的边缘($0$ 或 $100$ 厘米处)则会从木棒上坠落下去。
在某一时刻蚂蚁的位置各不相同且均在整数厘米处(即 $1,2,3,…99$ 厘米),有且只有一只蚂蚁 $A$ 速度为 $0$,其他蚂蚁均在向左或向右爬动。
给出该时刻木棒上的所有蚂蚁位置和初始速度,找出蚂蚁 $A$ 从此时刻到坠落所需要的时间。
输入格式
第一行包含一个整数表示蚂蚁的个数 $N$,之后共有 $N$ 行,每一行描述一只蚂蚁的初始状态。
每个初始状态由两个整数组成,中间用空格隔开,第一个数字表示初始位置厘米数 $P$,第二个数字表示初始方向,$−1$ 表示向左,$1$ 表示向右,$0$ 表示静止。
输出格式
蚂蚁 $A$ 从开始到坠落的时间。若不会坠落,输出 Cannot fall!
。
数据范围
$2≤N≤99,$
$1≤P≤99$
输入样例
4
10 1
90 0
95 -1
98 -1
输出样例
98
算法
$O(N)$
这道题似乎可以模拟,但是要同时维护 $100$ 个点,让人头大。
那么如何简化呢?
在模拟的过程中,有可能会发生这种情况:
$\small{(图片不来源于网络)}$
不喜勿喷!!
可以发现,图中的 $X,Y$ 蚂蚁碰头后交换了速度,向反方向移动。
再看这张↓
$\small{(图片不来源于网络)}$
当我们将编号遮住时,$X,Y$ 蚂蚁碰头后不像是交换了速度,像是直接穿过了对方。
这样说来,“如果两只蚂蚁碰头,则它们立即交换速度并继续爬动。”这个操作,仅对与 $A$ 蚂蚁有关的碰头操作有效。其他碰头操作,一律可以不用管。
再根据以上的结论,我们可以找到两类蚂蚁:
在 $A$ 左边而往左走的蚂蚁,在 $A$ 右边而往右走的蚂蚁。
我们可以把两类蚂蚁直接扔掉了,因为它们注定见不到 $A$ 蚂蚁。
$\small{(图片不来源于网络)}$
进行完上面的操作后,除 $A$ 外剩下的每只蚂蚁都有可能与 $A$ 碰头。
对于与 $A$ 有关的碰头操作,$A$ 每碰一次头,就会改变一次方向。
接下来进行分类讨论:
- 当 $A$ 左边和右边蚂蚁数量相等。这时,左右的蚂蚁对 $A$ 的影响抵消,最终 $A$ 停在原地。
- 当 $A$ 左边蚂蚁数量更多。右边的蚂蚁被全部抵消,最终 $A$ 从右侧掉下。
- 当 $A$ 右边蚂蚁数量更多。左边的蚂蚁被全部抵消,最终 $A$ 从左侧掉下。
最后一张(难看的)图了忍一忍!
$\small{(图片还是不来源于网络)}$
对于情况 $2$ 和 $3$,$A$ 的路程要找到较少边蚂蚁被全部抵消后 $A$ 碰到的较多边的第一只蚂蚁,坠落时间即为此蚂蚁无阻碍走完全程所需要的时间。
(这句话是抄的,因为我不太知道怎么表述)
时间复杂度
输入、分类的时间复杂度为 $O(N)$。
分类后,可以用 $O(1)$ 的时间直接找到 $A$ 的路程。
固时间复杂度为 $O(N)$。
C++ 代码
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
struct ant{ //结构体,代表一只蚂蚁
int spd, pla; //spd: 蚂蚁的方向,pla: 蚂蚁的初始位置
bool id; //id: 是否为A蚂蚁
};
bool cmp(ant a, ant b){ //比较函数,sort用
return a.pla < b.pla;
}
int main(){
int N;
scanf("%d", &N);
ant a[N]; //将所有数据存到这里
for(int i = 0; i < N; i++){
scanf("%d%d", &a[i].pla, &a[i].spd); //输入蚂蚁的位置与方向信息
if(a[i].spd == 0) a[i].id = 1; //如果是A蚂蚁,id设为1
else a[i].id = 0;
}
sort(a, a+N, cmp); //对a排序,方便给蚂蚁分类
int l_cnt = 0, r_cnt = 0;
int l[N], r[N];
bool on_left = 1;
/*
l_cnt: 在A左边且向右走的蚂蚁的数量
r_cnt: 在A右边且向左走的蚂蚁的数量
l: 存储左边且向右走的蚂蚁
r: 存储右边且向左走的蚂蚁
on_left: 初始为1,代表在A左侧;变为0时代表在A右侧
*/
for(int i = 0; i < N; i++){ //分类
if(a[i].id == 1) on_left = 0; //遇到A,后面的蚂蚁都在A右边
else{
if(on_left){
if(a[i].spd > 0) l[l_cnt++] = i; //在A左边,向右走的蚂蚁
}else{
if(a[i].spd < 0) r[r_cnt++] = i; //在A右边,向左走的蚂蚁
}
}
}
if(l_cnt == r_cnt) //左右相等
printf("Cannot fall!\n"); //推出最终蚂蚁会停留在原地
if(l_cnt < r_cnt) //右边多
printf("%d\n", a[r[l_cnt]].pla); //在r数组里去掉前l_cnt个蚂蚁
if(l_cnt > r_cnt) //左边多
printf("%d\n", 100 - a[l[l_cnt-r_cnt-1]].pla); //在l数组里去掉后r_cnt个蚂蚁
return 0;
}
无注释 C++ 代码
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
struct ant{
int spd, pla;
bool id;
};
bool cmp(ant a, ant b){
return a.pla < b.pla;
}
int main(){
int N;
scanf("%d", &N);
ant a[N];
for(int i = 0; i < N; i++){
scanf("%d%d", &a[i].pla, &a[i].spd);
if(a[i].spd == 0) a[i].id = 1;
else a[i].id = 0;
}
sort(a, a+N, cmp);
int l_cnt = 0, r_cnt = 0;
int l[N], r[N];
bool on_left = 1;
for(int i = 0; i < N; i++){
if(a[i].id == 1) on_left = 0;
else{
if(on_left){
if(a[i].spd > 0) l[l_cnt++] = i;
}else{
if(a[i].spd < 0) r[r_cnt++] = i;
}
}
}
if(l_cnt == r_cnt)
printf("Cannot fall!\n");
if(l_cnt < r_cnt)
printf("%d\n", a[r[l_cnt]].pla);
if(l_cnt > r_cnt)
printf("%d\n", 100 - a[l[l_cnt-r_cnt-1]].pla);
return 0;
}
备注
思路真的是自己想的啊!
虽然抄了一点但你们应该能理解我吧
这图是最骚的
感谢 @秣荛 的支持~
感谢 @[次饭] 的支持~
感谢 @LUO_6 的支持~
感谢 @封禁用户 的支持~
感谢 @AB-IN 的支持~
hh画的很可爱啊~
感谢 @[我也想成为钢铁侠呀] 的支持~
感谢 @[芙拉蒂蕾娜] 的支持~
感谢 @AcWing2AK 的支持~
与刷赞
感谢 @[R_U_OK] 的支持~
stO
感谢 @[_小镇做题家] 的支持~
感谢 @1Wizzy 的支持~
p3
画得好可爱🥺感谢支持~
感谢 @HeXing 的支持~
感谢 @sheepice 的支持~
感谢 @即是破晓 的支持~
👍
感谢 @xiayutao 的支持~