NYOJ--蚂蚁感冒(第五届蓝桥杯)

古城微笑少年丶 2022-08-26 13:18 206阅读 0赞

## 蚂蚁感冒 ##

时间限制： 1000 ms  |  内存限制： 65535 KB

难度： 2

描述

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

输入

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

输出

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

样例输入

3
    5 -2 8
    5
    -10 8 -20 12 25

样例输出

1
    3

来源

[第五届蓝桥杯][Link 1]

解析：自己比较水，拿到题先想到的排序然后。。。。搜了博客发现两只蚂蚁相撞同时掉头可以看作穿过，这样想的话就简单多了，第一只蚂蚁不管方向朝哪它右边的蚂蚁只要向左走就可能碰撞感染(特殊情况除外)，同样，第一只蚂蚁左边的蚂蚁只要朝右边走也可能被感染，这样就很容易得到这样的公式

ans = 左边蚂蚁向右走的数量+右边蚂蚁向左走的数量+第一只蚂蚁本身=right+left+1；

特殊情况是，当当第一只蚂蚁向左走的时候如果第一只蚂蚁左边没有向右爬行的蚂蚁，那么不管第一只蚂蚁右边有多少向左爬行的，因爬行的速度相同则右边的蚂蚁永远不可能被感染

同样的，当第一只蚂蚁向右走的时候，如果第一只蚂蚁右边没有向左爬行的蚂蚁，那么同样第一只蚂蚁左边也永远不可能感染

感觉说的好拗口不知道大家能看懂这个思路么

其实就是当第一只蚂蚁向左走且right为0时ans=1，相反也是这样的。

注明：该题的思路来源于博文[http://blog.csdn.net/y990041769/article/details/21941711][http_blog.csdn.net_y990041769_article_details_21941711]，谢谢这篇博文的作者。

下面贴一下自己写的代码

#include <iostream>
    using std::endl;
    using std::cout;
    using std::cin;
    int abs(int x)
    {
    	if(x<0)
    		return -x;
    	return x;
    }
    int main()
    {
    	int N;
    	int data[50];
    	while(cin >> N)
    	{
    		//感冒蚂蚁的数量
    		int left=0,right=0;
    		//输入数据
    		for(int i=0; i<N; ++i)
    		{
    			cin >> data[i];
    		}
    		for(int i=1; i<N;++i)
    		{
    			//找到该蚂蚁右边且向左走的
    			if(data[i]<0&&abs(data[i])>abs(data[0]))
    			{
    				left++;
    			}
    			//找到该蚂蚁左边且向右走的
    			if(data[i]>0&&abs(data[i])<abs(data[0]))
    			{
    				right++;
    			}
    		}
    		//判断是否为特殊情况
    		if((data[0]<0&&right==0)||(data[0]>0&&left==0))
    		{//见上面解析
    			cout << "1" <<endl;
    		}else
    		{
    			cout << left+right+1 << endl;
    		}
    	}
    	return 0;
    }

[Link 1]: http://acm.nyist.edu.cn/JudgeOnline/search_result.php?source=%E7%AC%AC%E4%BA%94%E5%B1%8A%E8%93%9D%E6%A1%A5%E6%9D%AF
[http_blog.csdn.net_y990041769_article_details_21941711]: http://blog.csdn.net/y990041769/article/details/21941711