P8611 [蓝桥杯 2014 省 AB] 蚂蚁感冒 题解

· · 题解

题目传送门

博客食用更佳

我们先来讲一下思路

有两种思路，第一种是模拟，使用将每一格看成2格的策略来避免相邻两格的相遇。每次重复两次走动，枚举来判断两只蚂蚁是否在同一个地方。

#include<bits/stdc++.h>
using namespace std;
typedef struct
{
    int x;//坐标
    bool ill;//是否感染
    int dir;//方向
}ant;
ant a[51];
int n;
bool allout()
{
    for(int i=1;i<=n;i++)
        if((a[i].x>=0)&&(a[i].x<=200))//如果有一个蚂蚁没有出界，那么就不能停
            return false;
    return true;
}
int check()
{
    int sum=0;
    for(int i=1;i<=n;i++)
        if(a[i].ill) sum++;//统计生病数量
    return sum;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i].x,a[i].ill=(i==1),a[i].dir=(a[i].x/abs(a[i].x)),a[i].x=abs(a[i].x)*2;//通过绝对值来初始化蚂蚁
    while(!allout())//当所有蚂蚁还没有出界，就执行操作
    {
        for(int i=1;i<=2;i++)//重复走两次，避免交错
        {
            for(int i=1;i<=n;i++)
                a[i].x+=a[i].dir;//走1或-1
            for(int i=1;i<n;i++)//判断两个蚂蚁是否重叠
                for(int j=i+1;j<=n;j++)
                    if(a[i].x==a[j].x)//如果坐标相同
                    {
                        a[i].dir=a[i].dir-a[i].dir-a[i].dir,a[j].dir=a[j].dir-a[j].dir-a[j].dir,a[i].ill=a[j].ill=((a[i].ill||a[j].ill)?true:false);
                    }
        }
    }
    cout<<check();
}

第二种思路，如果一只蚂蚁在生病蚂蚁向边缘走的路上挡着，那么这个人肯定会被传染，既然两只蚂蚁都被感染了，那么它们会交换方向，他们的状态相同，也就不需要考虑交换方向的事了。

#include<bits/stdc++.h>
using namespace std;
int n,x,ill,sum=1;//蚂蚁数量，当前蚂蚁坐标，生病蚂蚁坐标，感染数量
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    cin>>ill;
    for(int i=1;i<n;i++)
        cin>>x,sum+=((abs(x)<abs(ill)&&x>0)||(abs(x)>abs(ill)&&x<0));//第一种情况是当前的蚂蚁比生病的蚂蚁更靠左
    //第二种情况是当前蚂蚁比生病蚂蚁更靠右，但是生病蚂蚁得往右
    cout<<sum;
}

本蒟蒻第二次写题解，有错误请指正，如果有好的思路，也请评论，谢谢！

拜拜