问题描述
长 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
问题描述
题解:
首先, 将所有蚂蚁按在杆子上的位置从小到大排序;
从左向右依次便利每一只蚂蚁, 并判断当前蚂蚁离开杆子时是否患有感冒;
AC 代码:
- #include<iostream>
- #include<cstdio>
- #include<algorithm>
- #include<cstring>
- using namespace std;
- #define mem(a,b) memset(a,b,sizeof(a))
- const int maxn=200;
- int n;
- struct Date
- {
- bool dir;//1: 向右走; 0: 向左走
- int pos;
- bool isCold;//true:cold;false:no cold
- Date(int dir=0,int pos=0,int isCold=0):dir(dir),pos(pos),isCold(isCold){}
- }ant[maxn];
- bool cmp(Date _a,Date _b)
- {
- return _a.pos <_b.pos;
- }
- int Solve()
- {
- sort(ant+1,ant+n+1,cmp);
- int index=1;
- int ans=0;
- while(index <= n)// 从左边开始
- {
- if(!ant[index].dir)// 左边的蚂蚁向左走, 直接爬出杆子
- {
- ans += (ant[index].isCold ? 1:0);
- index++;
- }
- else// 左边的蚂蚁向右走
- {
- int t=index+1;
- while(t <= n && ant[t].dir)// 找到其右边的最先向左走的蚂蚁
- t++;
- if(t == n+1)//t == n+1, 说明当前杆子上剩余的蚂蚁全部向右走, 直接爬出杆子
- {
- for(int i=index;i < t;++i)
- ans += ant[i].isCold;
- break;
- }
- // 更新 [index,t-1] 之间蚂蚁的 isCode 和 dir
- for(int i=t-1;i>= index;--i)
- {
- if(ant[i].isCold || ant[i+1].isCold)
- ant[i].isCold=ant[i+1].isCold=true;
- ant[i].dir=!ant[i].dir;
- ant[i+1].dir=!ant[i+1].dir;
- }
- ans += (ant[index].isCold ? 1:0);// 判断当前蚂蚁是否感冒
- index++;// 爬出杆子
- }
- }
- return ans;
- }
- int main()
- {
- scanf("%d",&n);
- for(int i=1;i <= n;++i)
- {
- int x;
- scanf("%d",&x);
- ant[i]=Date(x> 0,abs(x),i == 1);
- }
- printf("%d\n",Solve());
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-2994199.html