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

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


目录
相关文章
|
6月前
|
算法 Java C++
蚂蚁感冒(蓝桥杯)
蚂蚁感冒(蓝桥杯)
34 0
|
6月前
|
消息中间件 缓存 NoSQL
记一次蚂蚁金服四面遭虐,面试水太深,过河的渡船你造好了吗?
有道无术,术可成;有术无道,止于道;以术识道,以道御术
|
机器人
LeetCode 双周赛 106(2023/06/10)两道思维题
往期回顾:[LeetCode 单周赛第 348 场 · 数位 DP 模版学会了吗?](https://mp.weixin.qq.com/s/4aLHpyaLOUEHSaX2X8e5FQ)
87 0
LeetCode 双周赛 106(2023/06/10)两道思维题
|
机器学习/深度学习 C++
蓝桥杯C++小朋友崇拜圈
蓝桥杯C++小朋友崇拜圈
111 0
|
Shell 计算机视觉
2021年中国大学生程序设计竞赛女生专场C. 连锁商店(状压dp 思维 贪心)
2021年中国大学生程序设计竞赛女生专场C. 连锁商店(状压dp 思维 贪心)
154 0
【蓝桥真题3】蓝桥改革变难,想进国赛这些能力你可缺一不可(下)
【蓝桥真题3】蓝桥改革变难,想进国赛这些能力你可缺一不可
233 0
【蓝桥真题3】蓝桥改革变难,想进国赛这些能力你可缺一不可(下)
|
大数据 程序员 云计算
世界程序员最难的题目,做不好你就是杀人凶手【云计算 大数据 开卷题目】
这道题目没有任何数据给你,但你可以去找估计数字,欢迎有志程序员做这到题目,这是一个开卷题目,你考虑的越多对象和属性程序会越复杂,你可以纯属娱乐。
|
Java
【蓝桥真题3】蓝桥改革变难,想进国赛这些能力你可缺一不可(上)
【蓝桥真题3】蓝桥改革变难,想进国赛这些能力你可缺一不可
181 0
|
算法 大数据 API
【蓝桥真题3】蓝桥改革变难,想进国赛这些能力你可缺一不可(中)
【蓝桥真题3】蓝桥改革变难,想进国赛这些能力你可缺一不可
197 0
|
存储 供应链 负载均衡
区块链需要迈过的几道坎
区块链需要迈过的几道坎
190 0
区块链需要迈过的几道坎
下一篇
无影云桌面