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

Vct14 · 2022-10-24 21:04:00 · 题解

我们先来分析一下样例 2 。

其中 L 表示向左， R 表示向右， G 表示感冒。

最后第 1,2,4 只蚂蚁感冒。

由表格可以发现，由于碰面就掉头，这些蚂蚁的相对排列顺序是保持不变的，那么，应该可以从开始的位置就能预测谁会被传染。

在样例 2 中，第 1 只蚂蚁（感冒蚂蚁）朝左。

1. 位于第 1 只蚂蚁左侧且朝右蚂蚁有一只，即第 2 只蚂蚁，被传染；
2. 由于步骤 1 ，第 1 只蚂蚁朝右，位于第 1 只蚂蚁右侧且朝左蚂蚁也有一只，即第 4 只蚂蚁，也被传染。

再举个第 1 只蚂蚁朝右的例子。

10 8 20 -12 -25

最后第 1,2,3,4 只蚂蚁感冒。

在这个例子中第 1 只蚂蚁（感冒蚂蚁）朝右。

1. 位于第 1 只蚂蚁右侧且朝左蚂蚁有两只，即第 4 只蚂蚁和第 5 只蚂蚁，它们都被传染；（其中第 3 只蚂蚁在与第 5 只蚂蚁碰面后朝左）
2. 由于步骤 1 ，第 1 只蚂蚁朝左，位于第 1 只蚂蚁左侧且朝右蚂蚁有一只，即第 2 只蚂蚁，也被传染。

总结以上两个例子：

设被感染的蚂蚁数为 n ，第 1 只蚂蚁左侧朝右的蚂蚁数为 x ，第 1 只蚂蚁右侧朝左的蚂蚁数为 y。

1. 第 1 只蚂蚁朝左时，

① x≠0 时， n=x+y+1；

② x=0 时， n=1；

2. 第 1 只蚂蚁朝右时，

① y≠0 时， n=x+y+1；

② y=0 时， n=1 。

代码：

#include<bits/stdc++.h>
using namespace std;

int x[55];

int main(){
    int n;
    cin>>n;
    for(int i=1; i<=n; i++) scanf("%d",&x[i]);
    int l=0,r=0;
    for(int i=2; i<=n; i++){
        if(abs(x[i])<abs(x[1]) && x[i]>0) l++;
        if(abs(x[i])>abs(x[1]) && x[i]<0) r++;
    }
    int sum=0;
    if(x[1]<0){
        if(l==0) sum=1;
        else sum=l+r+1;
    }
    else{
        if(r==0) sum=1;
        else sum=l+r+1;
    }
    cout<<sum;
    return 0;
}

注释版：

#include<bits/stdc++.h>
using namespace std;

int x[55];//定义蚂蚁数组

int main(){
    int n;//定义蚂蚁数
    cin>>n;//输入蚂蚁数
    for(int i=1; i<=n; i++) scanf("%d",&x[i]);//输入每个蚂蚁的情况
    int l=0,r=0;//统计在第1只蚂蚁左侧朝右、右侧朝左的蚂蚁数。
    for(int i=2; i<=n; i++){
        if(abs(x[i])<abs(x[1]) && x[i]>0) l++;//左侧朝右
        if(abs(x[i])>abs(x[1]) && x[i]<0) r++;//右侧朝左
    }
    int sum=0;//定义感冒蚂蚁总数
    if(x[1]<0){//第1只蚂蚁朝左
        if(l==0) sum=1;
        else sum=l+r+1;
    }
    else{//第1只蚂蚁朝右
        if(r==0) sum=1;
        else sum=l+r+1;
    }
    cout<<sum;//输出
    return 0;//华丽结束
}