蓝桥杯蚂蚁感冒

2019-11-06 07:20:42

字体：大中小

来源：转载

供稿：网友

/*标题：蚂蚁感冒长100厘米的细长直杆子上有n只蚂蚁。它们的头有的朝左，有的朝右。每只蚂蚁都只能沿着杆子向前爬，速度是1厘米/秒。当两只蚂蚁碰面时，它们会同时掉头往相反的方向爬行。这些蚂蚁中，有1只蚂蚁感冒了。并且在和其它蚂蚁碰面时，会把感冒传染给碰到的蚂蚁。请你计算，当所有蚂蚁都爬离杆子时，有多少只蚂蚁患上了感冒。【数据格式】第一行输入一个整数n (1 < n < 50), 表示蚂蚁的总数。接着的一行是n个用空格分开的整数 Xi (-100 < Xi < 100), Xi的绝对值，表示蚂蚁离开杆子左边端点的距离。正值表示头朝右，负值表示头朝左，数据中不会出现0值，也不会出现两只蚂蚁占用同一位置。其中，第一个数据代表的蚂蚁感冒了。要求输出1个整数，表示最后感冒蚂蚁的数目。例如，输入：35 -2 8程序应输出：1再例如，输入：5-10 8 -20 12 25程序应输出：3

刚开始我想多了，想的比较复杂，后来参考人家的博客，才知道，两只蚂蚁碰头之后，相当于原来的蚂蚁方向没有改变，只是感冒的蚂蚁数目增加了，最后蚂蚁感冒的数目就可以得出了。

具体思路：

如果初始蚂蚁在左边，如果左边的蚂蚁都在向左走，速度都一样是不会感冒的，如果左边的蚂蚁有向右走的，这些向右走的蚂蚁都会感冒，然后这些蚂蚁的会传染所有右边向左走的蚂蚁，感冒的蚂蚁就是这些求和如果初始蚂蚁在右边也是一样的具体一下就是左边向右走的蚂蚁和右边向左走的蚂蚁都是会感冒的，最后再加上它自己

*/#include <cstdio>#include <algorithm>using namespace std;struct Node{int x;int dis;int num; } ; Node a[100]; int cmp(Node a1,Node a2) { if(a1.x != a2.x ) return a1.x < a2.x ; } int main() { int n,x; while(~scanf("%d",&n)) { for(int i=0; i<n;i++) { scanf("%d",&x); a[i].dis = x <0? -1:1;//-1表示向左走，1表示向右走a[i].x = abs(x);a[i].num = i+1; //数组下标 }sort(a,a+n,cmp) ;int temp=0,left=0,right=0,ans=0;for(int i=0;i<n;i++)//左边向右走的{if(a[i].num == 1){temp=i;//代表那只感冒的蚂蚁的位置break;} if(a[i].dis == 1)left++;}for (int i=temp+1;i<n;i++){if(a[i].dis ==-1)right++; } if(a[temp].dis==1 && right==0 || a[temp].dis==-1 && left==0) ans++; else ans=left+right+1; PRintf("%d/n",ans); } return 0; }

上一篇：sdutacm-图结构练习——最小生成树

下一篇：sdutacm-数据结构实验：连通分量个数