日志

蓝桥杯 试题 历届试题 蚂蚁感冒

 来源    2020-05-23    0  
问题描述
  长100厘米的细长直杆子上有n只蚂蚁。它们的头有的朝左,有的朝右。

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

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

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

  请你计算,当所有蚂蚁都爬离杆子时,有多少只蚂蚁患上了感冒。
输入格式
  第一行输入一个整数n (1 < n < 50), 表示蚂蚁的总数。

  接着的一行是n个用空格分开的整数 Xi (-100 < Xi < 100), Xi的绝对值,表示蚂蚁离开杆子左边端点的距离。正值表示头朝右,负值表示头朝左,数据中不会出现0值,也不会出现两只蚂蚁占用同一位置。其中,第一个数据代表的蚂蚁感冒了。
输出格式
  要求输出1个整数,表示最后感冒蚂蚁的数目。
样例输入
3
5 -2 8
样例输出
1
样例输入
5
-10 8 -20 12 25
样例输出
3

这一题与 POJ No.1852(Ant)思路相似,首先来看一下POJ的题目:
题目描述:
因为题目难抄,所以直接用了https://blog.csdn.net/qq_43751506/article/details/105836389这位朋友的图片,我也是在一起来挑战程序设计这本书中看到这一题的。
如果暴力搜索所有蚂蚁向左或向右两种可能,则有2^n复杂度,指数爆炸。
首先考虑最短时间:所有的蚂蚁应该都朝向离自己近的一端爬行,即以左端为坐标0点,则[ 0, L/2 ] 的蚂蚁应该朝左爬, (L/2, L ] 的蚂蚁应该朝右爬。这时没有蚂蚁相遇的情况。
接下来思考最长时间。
如果直接考虑一个蚂蚁不间断的相遇,改变自己的方向...会让问题变得很复杂。实际上,我们考虑的是最长时间,而不是某个蚂蚁的状态。
如果忽略了蚂蚁之间的区别,可以认为两个蚂蚁相遇时是保持原方向交错而过。
这样思考问题就简单多了:最长时间即蚂蚁离端点的最远距离。
主要代码:
//输入
int n,L;
int x[Max_N];//保存蚂蚁的位置

void solve()
{
    int Min_T = 0, Max_T = 0;
    
    for(int i=0; i<n; i++)
    {
        Min_T = max( Min_T, min(x[i],L-x[i])); //计算最短时间 
        Max_T = max( Max_T, max(x[i],L-x[i]));//计算最长时间 
    }
    printf("%d %d\n",Min_T,Max_T);
}

在回头看这道蓝桥杯题:当蚂蚁相遇时,同样可以视为没有改变方向交错而过,只是和感冒的蚂蚁相遇后另一只也会感冒。

考虑两种情况:

  • 第一个数据为正值( 第一只感冒的蚂蚁头朝右 )
首先看第一只感冒的蚂蚁的右端:因为我们考虑的是蚂蚁相遇后仍按原方向移动,那么对于第一只感冒蚂蚁右侧方向也向右的蚂蚁不会被感染( 画×的蚂蚁)
而右侧方向向左的蚂蚁会与第一只蚂蚁相遇而感冒。
之后再看左侧:左侧的蚂蚁这时可能会被右侧画√的蚂蚁感染。但左侧方向也向左的不会被感染(速度相同,追不上),只有左侧方向向右的蚂蚁会被感染。
  • 再看第一个数据为负值(即第一只感冒的蚂蚁头朝左)

首先看左侧蚂蚁,思路相同,左侧方向向右的蚂蚁最终会被感染,而向左的不会。

之后看右侧,右侧蚂蚁可能会被左侧画√的蚂蚁感染,但只有右侧方向向左的。


综合这两张图可以很发现:在第一只感冒蚂蚁左侧方向向右的会被感染;右侧方向向左的会被感染。所以代码就非常简单。

实现代码:
#include<cstdio>
 
//其实只要求在感冒位置左边方向向右;右边方向向左的个数就可以了 

const int Max_N = 50;

int n;
int x[Max_N+1];// 0:没有蚂蚁 -1:向左  1:向右 

int ant; //感冒蚂蚁的位置 

void solve()
{
    int res = 0;
    for(int i=1; i<ant; i++){//左边 向右 
        if( x[i]==1 )    res++;
    }
    for(int i=ant+1; i<=100; i++){//右边 向左 
        if( x[i]==-1 )    res++;
    }
    printf("%d\n",res+1);//加上原来的第一只感冒的蚂蚁 
}

int main()
{
    scanf("%d",&n);
    int a;
    scanf("%d",&a);
    ant = a>0 ? a : -a;//第一个位置是感冒的位置
    while( --n )
    {//剩下的n-1个 
        scanf("%d",&a);
        if( a>0 )    x[a] = 1;//向右
        else    x[-a] = -1; //向左 
    } 
    
    solve();
    
    return 0;
}

蓝桥杯: 历届试题 小朋友排队 (树状数组,逆序对,思维)
日志  历届试题 小朋友排队   时间限制:1.0s   内存限制:256.0MB 问题描述 n 个小朋友站成一排.现在要把他们按身高从低到高的顺序排列,但是每次只能交换位置相邻的两个小朋友. 每个小朋友 ...
1
14年第五届蓝桥杯第七题_蚂蚁感冒_(思维)
日志长100厘米的细长直杆子上有n只蚂蚁.它们的头有的朝左,有的朝右. 每只蚂蚁都只能沿着杆子向前爬,速度是1厘米/秒. 当两只蚂蚁碰面时,它们会同时掉头往相反的方向爬行. 这些蚂蚁中,有1只蚂蚁感冒了. ...
1
蓝桥杯历届《蚂蚁感冒》
日志问题描述 长100厘米的细长直杆子上有n只蚂蚁.它们的头有的朝左,有的朝右. 每只蚂蚁都只能沿着杆子向前爬,速度是1厘米/秒. 当两只蚂蚁碰面时,它们会同时掉头往相反的方向爬行. 这些蚂蚁中,有1只蚂 ...
2016年第七届蓝桥杯javaB组 试题 答案 解析
日志1.煤球数目 有一堆煤球,堆成三角棱锥形.具体: 第一层放1个, 第二层3个(排列成三角形), 第三层6个(排列成三角形), 第四层10个(排列成三角形), .... 如果一共有100层,共有多少个煤 ...
1
2015年第六届蓝桥杯javaB组 试题 答案 解析
日志1.三角形面积 如图1所示.图中的所有小方格面积都是1. 那么,图中的三角形面积应该是多少呢? 请填写三角形的面积.不要填写任何多余内容或说明性文字. ##### 答案 : 28 ### 2.立方变自 ...
2014年第五届蓝桥杯javaB组 试题 答案 解析
日志1.武功秘籍 小明到X山洞探险,捡到一本有破损的武功秘籍(2000多页!当然是伪造的).他注意到:书的第10页和第11页在同一张纸上,但第11页和第12页不在同一张纸上. 小明只想练习该书的第81页到 ...
2013年第四届蓝桥杯javaB组 试题 答案 解析
日志1.世纪末的星期 曾有邪教称1999年12月31日是世界末日.当然该谣言已经不攻自破. 还有人称今后的某个世纪末的12月31日,如果是星期一则会.... 有趣的是,任何一个世纪末的年份的12月31日都 ...
黑马程序员-第五届蓝桥杯校内选拔试题和 答案
日志/*一.坡度问题 有一段均匀的上坡路,长度刚好是1公里.某辆汽车从坡下开到坡顶,车上的气压表显示,海拔高度减少了49米. 求这段坡路的平均坡度(用度表示,尽量精确) 以下代码片段实现了该功能,请填写划 ...
1
2018年第九届蓝桥杯国赛试题(JavaA组)
日志1.结果填空 (满分13分)2.结果填空 (满分39分)3.代码填空 (满分27分)4.程序设计(满分45分)5.程序设计(满分71分)6.程序设计(满分105分)  1.标题:三角形面积 已知三角形 ...
1
2017年第八届蓝桥杯国赛试题(JavaA组)
日志1.结果填空 (满分19分)2.结果填空 (满分47分)3.代码填空 (满分21分)4.程序设计(满分35分)5.程序设计(满分79分)6.程序设计(满分99分)  1.标题:图书排列 将编号为1~1 ...
2016年第七届蓝桥杯国赛试题(JavaA组)
日志1.结果填空 (满分19分)2.结果填空 (满分35分)3.代码填空 (满分21分)4.程序设计(满分47分)5.程序设计(满分79分)6.程序设计(满分99分)  1.阶乘位数 9的阶乘等于:362 ...
1
2015年第六届蓝桥杯国赛试题(JavaA组)
日志1.结果填空 (满分15分)2.结果填空 (满分35分)3.代码填空 (满分31分)4.程序设计(满分41分)5.程序设计(满分75分)6.程序设计(满分103分)  1.标题:胡同门牌号 小明家住在 ...
1
2014年第五届蓝桥杯国赛试题(JavaA组)
日志1.结果填空 (满分15分)2.结果填空 (满分45分)3.代码填空 (满分30分)4.程序设计(满分30分)5.程序设计(满分80分)6.程序设计(满分100分)  1.标题:海盗分金币     有 ...
1
2013年第四届蓝桥杯国赛试题(JavaA组)
日志1.结果填空 (满分12分)2.结果填空 (满分15分)3.结果填空 (满分10分)4.程序设计(满分16分)5.程序设计(满分20分)6.程序设计(满分27分)  1.标题:填算式     请看下面 ...
2017年第八届蓝桥杯省赛试题(JavaA组)
日志1.结果填空 (满分5分)2.结果填空 (满分11分)3.结果填空 (满分13分)4.结果填空 (满分17分)5.代码填空 (满分7分)6.代码填空 (满分9分)7.程序设计(满分19分)8.程序设计 ...
2016年第七届蓝桥杯省赛试题(JavaA组)
日志1.结果填空 (满分3分)2.结果填空 (满分5分)3.结果填空 (满分9分)4.代码填空 (满分11分)5.代码填空 (满分13分)6.结果填空 (满分15分)7.结果填空 (满分19分)8.程序设 ...
1
2015年第六届蓝桥杯省赛试题(JavaA组)
日志1.结果填空 (满分3分)2.结果填空 (满分5分)3.结果填空 (满分9分)4.代码填空 (满分11分)5.代码填空 (满分13分)6.结果填空 (满分17分)7.结果填空 (满分21分)8.程序设 ...
1
2014年第五届蓝桥杯省赛试题(JavaA组)
日志1.结果填空 (满分2分)2.结果填空 (满分6分)3.结果填空 (满分7分)4.代码填空 (满分4分)5.代码填空 (满分12分)6.结果填空 (满分12分)7.结果填空 (满分9分)8.程序设计( ...
2013年第四届蓝桥杯省赛试题(JavaA组)
日志1.结果填空 (满分3分)2.结果填空 (满分5分)3.结果填空 (满分6分)4.结果填空 (满分13分)5.代码填空 (满分5分)6.代码填空 (满分10分)7.程序设计(满分4分)8.程序设计(满 ...
蓝桥杯 历届试题 蚂蚁感冒
日志  历届试题 蚂蚁感冒   时间限制:1.0s   内存限制:256.0MB      问题描述 长100厘米的细长直杆子上有n只蚂蚁.它们的头有的朝左,有的朝右. 每只蚂蚁都只能沿着杆子向前爬,速度 ...