题目描述
长 $100$ 厘米的细长直杆子上有 $n$ 只蚂蚁。
它们的头有的朝左,有的朝右。
每只蚂蚁都只能沿着杆子向前爬,速度是 $1$ 厘米/秒。
当两只蚂蚁碰面时,它们会同时掉头往相反的方向爬行。
这些蚂蚁中,有 $1$ 只蚂蚁感冒了。
并且在和其它蚂蚁碰面时,会把感冒传染给碰到的蚂蚁。
请你计算,当所有蚂蚁都爬离杆子时,有多少只蚂蚁患上了感冒。
输入格式
第一行输入一个整数 $n$, 表示蚂蚁的总数。
接着的一行是 $n$ 个用空格分开的整数 $X_i$, $X_i$ 的绝对值表示蚂蚁离开杆子左边端点的距离。
正值表示头朝右,负值表示头朝左,数据中不会出现 $0$ 值,也不会出现两只蚂蚁占用同一位置。
其中,第一个数据代表的蚂蚁感冒了。
输出格式
输出1个整数,表示最后感冒蚂蚁的数目。
数据范围
$1 < n < 50$,
$0 < |X_i| < 100$
输入样例1:
3
5 -2 8
输出样例1:
1
输入样例2:
5
输出样例2:
3
思路
两只蚂蚁相遇可以认为,它们之间发生了灵魂互换,也即可看作还是原先的两只蚂蚁,
只不过穿透了对方的身体,
按上述方式考虑后,问题就变得简单多了。
将所有的蚂蚁,按其在木杆上的位置排好序(不管方向)
首先,我们先发动时间静止魔法,让感冒的蚂蚁先走出细杆,
并记录它是否途径了和它面对面的蚂蚁,这些蚂蚁都会被感染。
如果,感冒的蚂蚁一只蚂蚁也没传染,则最终答案就是1
否则的话,还需要考虑不在上述感冒蚂蚁路径上的蚂蚁,
如果,它们的方向和感冒的蚂蚁相同的话,
一定会被先前感冒蚂蚁途径路径上的蚂蚁感染
最后输出感冒的蚂蚁数量
时间复杂度
O(n*logn)
空间复杂度
O(n)
C++ 代码
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 55;
int ant[N];
int infect;
int n;
bool cmp(int &a,int &b)
{
return abs(a)<=abs(b);
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i = 1;i <= n;i ++)
{
cin>>ant[i];
if(i == 1) infect = ant[1];
}
sort(ant + 1,ant + n + 1 , cmp);//按绝对值升序排序
//感冒的蚂蚁初始方向向左
if(infect < 0)
{
int res = 1;
for(int i = 1;ant[i] != infect;i ++)
{
if(ant[i] > 0) res++;
}
if(res == 1)
{
cout<<res<<endl;
return 0;
}
else
{
for(int i = n;ant[i] != infect;i --)
{
if(ant[i] < 0) res++;
}
cout<<res<<endl;
return 0;
}
}
else if(infect > 0)//感冒的蚂蚁初始方向向右
{
int res = 1;
for(int i = n;ant[i] != infect;i --)
{
if(ant[i] < 0) res++;
}
if(res == 1)
{
cout<<res<<endl;
return 0;
}
else
{
for(int i = 1;ant[i] != infect;i ++)
{
if(ant[i] > 0) res++;
}
cout<<res<<endl;
return 0;
}
}
return 0;
}