小思维题-蚂蚁感冒——蓝桥杯

简介: Description长100厘米的细长直杆子上有n只蚂蚁。它们的头有的朝左,有的朝右。每只蚂蚁都只能沿着杆子向前爬,速度是1厘米/秒。当两只蚂蚁碰面时,它们会同时掉头往相反的方向爬行。这些蚂蚁中,有1只蚂蚁感冒了。并且在和其它蚂蚁碰面时,会把感冒传染给碰到的蚂蚁。请你计算,当所有蚂蚁都爬离杆子时,有多少只蚂蚁患上了感冒。
[蚂蚁感冒](https://www.acwing.com/problem/content/description/1213/)


Description


长100厘米的细长直杆子上有n只蚂蚁。它们的头有的朝左,有的朝右。

每只蚂蚁都只能沿着杆子向前爬,速度是1厘米/秒。

当两只蚂蚁碰面时,它们会同时掉头往相反的方向爬行。

这些蚂蚁中,有1只蚂蚁感冒了。并且在和其它蚂蚁碰面时,会把感冒传染给碰到的蚂蚁。

请你计算,当所有蚂蚁都爬离杆子时,有多少只蚂蚁患上了感冒。


Input


第一行输入一个整数n (1<n<50), 表示蚂蚁的总数。

接着的一行是n个用空格分开的整数 Xi (−100<Xi<100), Xi的绝对值,表示蚂蚁离开杆子左边端点的距离。正值表示头朝右,负值表示头朝左,数据中不会出现0值,也不会出现两只蚂蚁占用同一位置。==其中,第一个数 据代表的蚂蚁感冒了。 ==


Output


要求输出1个整数,表示最后感冒蚂蚁的数目。


Samples


Input


3 
5  -2  8 


Output


1


Input


5 
-10  8  -20  12  25


Output


3


第一只蚂蚁是感冒的,其次,两只蚂蚁在相遇的时候,相互掉头,这时候可以看做是继续向前走,当成穿过对面的蚂蚁,这样的结果是等效的。

因为所有的蚂蚁速度都是相等的,所以之后方向相反的情况才会相遇并且传染。

那么来说,如果第一号蚂蚁如果是向右走的,那么他右面的蚂蚁中向左走的就会被感染,此时要加上这只蚂蚁右面的蚂蚁中向左走的蚂蚁数量;如果一号蚂蚁是向左走的,那么在这只蚂蚁左面的蚂蚁中向右走的蚂蚁就要被感染,此时数量要加上在这只蚂蚁左面并且向右走的蚂蚁的数量。

特殊的情况是如果上面的两种情况中,有一种右面没有蚂蚁出现,此时就是这蚂蚁自己感冒,输出 1


Main_Code


    int n=read;
    for(int i=1;i<=n;i++) a[i]=read;
    int t1=0,t2=0;
    for(int i=2;i<=n;i++){
        if(a[i] > 0 && abs(a[i]) < abs(a[1])) t1++;
        else if(a[i] < 0 && abs(a[i]) > abs(a[1])) t2++;
    }
    if(a[1] < 0 && t1 == 0) cout<<1<<endl;
    else if(a[1] > 0 && t2 == 0) cout<<1<<endl;
    else cout<<t1+t2+1<<endl;


文章知识点与官方知识档案匹配,可进一步学习相关知识

算法技能树蓝桥杯-基础切面条7034 人正在系统学习中


目录
相关文章
|
9月前
|
机器学习/深度学习 存储 人工智能
【c++百日刷题计划】 ———— DAY12,奋战百天,带你熟练掌握基本算法
【c++百日刷题计划】 ———— DAY12,奋战百天,带你熟练掌握基本算法
168 0
|
3月前
|
算法 Java C++
蚂蚁感冒(蓝桥杯)
蚂蚁感冒(蓝桥杯)
16 0
|
4月前
|
消息中间件 缓存 NoSQL
记一次蚂蚁金服四面遭虐,面试水太深,过河的渡船你造好了吗?
有道无术,术可成;有术无道,止于道;以术识道,以道御术
|
9月前
|
人工智能 算法 C++
【c++百日刷题计划】 ———— DAY11,奋战百天,带你熟练掌握基本算法
【c++百日刷题计划】 ———— DAY11,奋战百天,带你熟练掌握基本算法
83 0
|
9月前
|
存储 算法 C++
【c++百日刷题计划】 ———— DAY13,奋战百天,带你熟练掌握基本算法
【c++百日刷题计划】 ———— DAY13,奋战百天,带你熟练掌握基本算法
228 0
|
9月前
|
人工智能 算法 搜索推荐
【c++百日刷题计划】 ———— DAY10,奋战百天,带你熟练掌握基本算法
【c++百日刷题计划】 ———— DAY10,奋战百天,带你熟练掌握基本算法
174 0
|
9月前
|
机器学习/深度学习 算法 C++
【c++百日刷题计划】 ———— DAY8,奋战百天,带你熟练掌握基本算法
【c++百日刷题计划】 ———— DAY8,奋战百天,带你熟练掌握基本算法
145 0
|
9月前
|
算法 C++
【c++百日刷题计划】 ———— DAY14,奋战百天,带你熟练掌握基本算法
【c++百日刷题计划】 ———— DAY14,奋战百天,带你熟练掌握基本算法
147 0
|
9月前
|
人工智能 算法 BI
【c++百日刷题计划】 ———— DAY9,奋战百天,带你熟练掌握基本算法
【c++百日刷题计划】 ———— DAY9,奋战百天,带你熟练掌握基本算法
98 0
|
10月前
|
机器人
LeetCode 双周赛 106(2023/06/10)两道思维题
往期回顾:[LeetCode 单周赛第 348 场 · 数位 DP 模版学会了吗?](https://mp.weixin.qq.com/s/4aLHpyaLOUEHSaX2X8e5FQ)
63 0
LeetCode 双周赛 106(2023/06/10)两道思维题