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

简介: 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 人正在系统学习中


目录
相关文章
|
8月前
|
算法 Java C++
蚂蚁感冒(蓝桥杯)
蚂蚁感冒(蓝桥杯)
39 0
|
数据采集 人工智能 算法
2022年计算机保研夏令营经验总结,11所院校经历,预推免上岸北大
2022年计算机保研夏令营经验总结,11所院校经历,预推免上岸北大
|
机器人
LeetCode 双周赛 106(2023/06/10)两道思维题
往期回顾:[LeetCode 单周赛第 348 场 · 数位 DP 模版学会了吗?](https://mp.weixin.qq.com/s/4aLHpyaLOUEHSaX2X8e5FQ)
89 0
LeetCode 双周赛 106(2023/06/10)两道思维题
|
人工智能
看我今年奋斗,观我未来之路
看我今年奋斗,观我未来之路
68 0
南桥杯:蚂蚁感冒
南桥杯:蚂蚁感冒
79 0
|
算法 程序员
【算法集训暑期刷题营】8.4日题---思维
【算法集训暑期刷题营】8.4日题---思维
【算法集训暑期刷题营】8.4日题---思维
AcWing 1211. 蚂蚁感冒
AcWing 1211. 蚂蚁感冒
72 0
|
算法
2021-2022年度第三届全国大学生算法设计与编程挑战赛(秋季赛)热身赛 B.这是一道大水题(树状数组)
2021-2022年度第三届全国大学生算法设计与编程挑战赛(秋季赛)热身赛 B.这是一道大水题(树状数组)
163 0
2021-2022年度第三届全国大学生算法设计与编程挑战赛(秋季赛)热身赛 B.这是一道大水题(树状数组)
|
机器学习/深度学习 人工智能 算法
2021-2022年度第三届全国大学生算法设计与编程挑战赛(秋季赛)G.希望(组合数学 bfs)
2021-2022年度第三届全国大学生算法设计与编程挑战赛(秋季赛)G.希望(组合数学 bfs)
254 0
2021-2022年度第三届全国大学生算法设计与编程挑战赛(秋季赛)G.希望(组合数学 bfs)
|
Shell 计算机视觉
2021年中国大学生程序设计竞赛女生专场C. 连锁商店(状压dp 思维 贪心)
2021年中国大学生程序设计竞赛女生专场C. 连锁商店(状压dp 思维 贪心)
165 0