试题 历届试题 蚂蚁感冒
提交此题 评测记录
资源限制
时间限制：1.0s 内存限制：256.0MB
问题描述
长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
土方法，1厘米1厘米的爬出结果，先凑合，等我再学学，后面再用好的数据结构算法，改良改良。未完待续。。。。。。
代码如下：
#include <iostream>
#include <cmath>
using namespace std;
#define INF 65535
struct AntNode{
int num;
int pos;
int direction;
bool isIll;
}ATS[50];
int n;
int G[101];
bool collected[51];
void ReadInput(){
cin>>n;
int xi;
for(int i=0;i<n;i++){
cin>>xi;
if(i==0){
ATS[i].isIll=true;
}
if(i>0)
ATS[i].isIll=false;
ATS[i].pos=abs(xi);
ATS[i].num=i;
if(xi>0){
ATS[i].direction=1;
}
if(xi<0){
ATS[i].direction=-1;
}
collected[i]=false;
}
for(int i=0;i<101;i++){
G[i]=INF;
}
}
void runOpt(){
int cnt=0;
int coldNum=1;
while(cnt<n){
for(int i=0;i<n;i++){
if(ATS[i].pos>0 && ATS[i].pos<100){
G[ATS[i].pos]=INF;
if(ATS[i].direction==1){
ATS[i].pos++;
}
if(ATS[i].direction==-1){
ATS[i].pos--;
}
if(G[ATS[i].pos]!=INF){
ATS[i].direction=-ATS[i].direction;
ATS[G[ATS[i].pos]].direction=-ATS[G[ATS[i].pos]].direction;
if( ( ATS[i].isIll==true && ATS[G[ATS[i].pos]].isIll==false ) || ( ATS[i].isIll==false && ATS[G[ATS[i].pos]].isIll==true ) ){
ATS[i].isIll=ATS[G[ATS[i].pos]].isIll=true;
coldNum++;
}
}
if( ATS[i].pos>0 && ATS[i].pos<100 && G[ATS[i].pos]==INF){
G[ATS[i].pos]=i;
}
}
else{
if(collected[i]==false){
cnt++;
collected[i]=true;
}
}
}
}
cout<<coldNum<<endl;
}
int main(int argc, char** argv) {
ReadInput();
runOpt();
return 0;
}