当前位置: 首页 > article >正文

蓝桥杯[每日一题] 模拟题:蚂蚁感冒(java版)

题目描述

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

输入格式

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

输出格式

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

数据范围

1<n<50,
0<|Xi|<100

 输入样例1

3
5 -2 8

输出样例1

1

输入样例2

5
-10 8 -20 12 25

输出样例2

3

解题思路

虽然题目说得那么绕,什么遇到相向而行的蚂蚁就掉头。但其实我们可以理解为他们俩没有相互掉头,而是直接穿过去了。 大家可以想象一下,比如你和小明相向而行,你们相遇之后,都掉头。但是如果站在远处看,能发现你们谁是谁吗,直接将你们两个看成一样的人,遇到之后掉头,和你们继续沿着原来的方向继续前进,效果其实是一样的。

如图,我们将中间那个圆点看作是最初感冒的蚂蚁,两边的箭头表示移动的蚂蚁。为什么我不画左边向左的,右边向右的?因为这些都不用考虑,他们压根不会被感染。如何理解呢,其实可以模拟一下,因为蚂蚁移速都是一样的,那么只要它移动方向的前方没有被感染的蚂蚁,那它就不会被感染的。

我们来分析一下蚂蚁的感染情况。

第一只蚂蚁向右:

右边向左的蚂蚁一定被感染。

右边向左的蚂蚁感染情况:

只有当存在右边向左的蚂蚁时,才会被感染。

第一只蚂蚁向左:

左边向右的蚂蚁一定被感染

右边向左的蚂蚁感染情况:

只有当存在左边向右的蚂蚁时,才会被感染。 

所以,我们先不管第一只蚂蚁朝哪个方向移动,我们先以第一只蚂蚁为分界线,把它左边的并且移动方向向右的,右边的并且移动方向向左的蚂蚁数量统计出来。 

统计出来之后,再分情况讨论。

不知道这个时候会不会有读者觉得,上面两种情况不是都差不多吗,那我能不能直接将两个数加起来,再把第一只蚂蚁加上,不就是答案了吗?博主刚开始就是这样干的,发现其实是不对的。

我们以第一只蚂蚁向右来看,如果直接将两个数加起来,再加上第一只蚂蚁的话,那答案就是leftToRight+RightToLeft+1。此时,如果右边向左的蚂蚁为0,那答案就是leftToRight+1。那答案就是大于等于1的。然而实际上,这种情况答案应该是1。这个过程可以想象一下,因为没有任何蚂蚁和第一只感冒的蚂蚁相撞,所以被感染的蚂蚁数并不会增加。第一只蚂蚁向左也是如此。所以正确的逻辑应该是:

第一只蚂蚁向右:

如果右边向左移动的蚂蚁数为0,答案就是1;

否则才是leftToRight+RightToLeft+1

第一只蚂蚁向左:

如果左边向右边移动的蚂蚁数为0,答案也是1;

否则才是leftToRight+RightToLeft+1

总结下来就是:

(第一只蚂蚁向左且右边向左移动的蚂蚁数为0)或者(第一只蚂蚁向左且左边向右边移动的蚂蚁数为0),答案就是1,否则就是leftToRight+RightToLeft+1。

代码实现

完整代码如下:

import java.io.IOException;
import java.io.*;

public class Main{
    public static void main(String[] args) throws IOException {
        Scanner scan=new Scanner(System.in);
        int n=scan.nextInt();
        int []nums=new int[n];
        for (int i = 0; i < n; i++) {
            nums[i]=scan.nextInt();
        }
        //先统计两边的蚂蚁
        int leftToRight=0;
        int rightToLeft=0;
        for (int i = 1; i < n; i++) {
            if(nums[i]>0&&Math.abs(nums[i])<Math.abs(nums[0]))
                leftToRight++;
            if(nums[i]<0&&Math.abs(nums[i])>Math.abs(nums[0])){
                rightToLeft++;
            }
        }
        if((nums[0]>0&&rightToLeft==0)||(nums[0]<0&&leftToRight==0))
            System.out.println(1);
        else System.out.println(leftToRight+rightToLeft+1);
    }
}



class Scanner {
    private BufferedReader bf;
    private StreamTokenizer st;

    public Scanner(InputStream inputStream) {
        bf = new BufferedReader(new InputStreamReader(inputStream));
        st = new StreamTokenizer(bf);
    }

    public int nextInt() throws IOException {
        st.nextToken();
        return (int) st.nval;
    }

    public String nextLine() throws IOException {
        return bf.readLine();
    }
}


http://www.kler.cn/a/589882.html

相关文章:

  • 项目实战系列:基于瑞萨RA6M5构建多节点OTA升级-系统设计<一>
  • ArcGIS Pro中加载在线地图的详细指南
  • 3.1 Spring Boot性能优化:从线程池调优到JVM参数配置
  • java web 安全,如何认证客户端?时间戳和noce如何抵御重放攻击?
  • 8051汇编--条件转移指令
  • 网络框架OkHttp与Retrofit原理剖析
  • Linux-c-粘住位
  • uni-app学习笔记——自定义模板
  • [Java实战]Spring Boot服务CPU 100%问题排查:从定位到解决
  • 爬虫逆向:详细讲述Android底层原理及机制
  • 职业教育五金建设改革解析
  • 0基础 | 直流稳压电源专题3
  • 【Spring】第二弹:通过反射机制初步理解 IoC
  • 本地电脑Java项目发布到公网
  • Java学习第十二天--集合
  • 嵌入式八股RTOS与Linux---前言篇
  • MySQL InnoDB引擎的锁机制详解
  • OceanBase 用户问题精选答疑:OceanBase 版本升级解析
  • 电机控制常见面试问题(十五)
  • 算法-除自身以外数组的乘积