Skip to main content

1211.蚂蚁感冒

tip

原题链接：https://www.acwing.com/problem/content/1213/

思路​

一般数学题利用等价的思想。（找规律）

这里可以把掉头看成穿过，也就是这个方向上的蚂蚁全都会感冒。分多种情况来讨论。分类讨论

第一个蚂蚁向右走的情况：

  1. 右边向左走的，必然被感染
  2. 右边向右走，必然不会被感染
  3. 左边向左走，必然不会被感染
  4. 左边向右走
    • 右边存在向左走，必然会被感染
    • 右边不存在向左走，必然不会被感染

所以本题核心思路就是忽略掉中间的细节，只要两只蚂蚁相互对撞，那他的左右两边一定是被感染的。如果两只蚂蚁同向，那么永远都不会感染。

info

如果有时候觉得细节太多的时候，试着把思路变换一下，我就不去抠里面的细节，我用等价的方式来思考。

代码​

#include <bits/stdc++.h>

using namespace std;

const int N = 55;

int n;
int x[N];

int main() {
    
    cin >> n;
    
    for (int i = 0 ;i < n; i++) cin >> x[i];
    
    int left = 0, right = 0; // 左边向右走，右边向左走的蚂蚁数量
    for (int i = 1;i < n; i++) {
        // abs(x[i]) < abs(x[0]) 判断当前蚂蚁i在左边还是右边，这里是左，第一个蚂蚁是向右走的
        // abs(x[i]) > abs(x[0]) 判断当前蚂蚁i在右边，并且第一个蚂蚁向左
        if (abs(x[i]) < abs(x[0]) && x[i] > 0) left++;
        else if (abs(x[i]) > abs(x[0]) && x[i] < 0) right++;
    }
    
    if (x[0] > 0 && right == 0 || x[0] < 0 && left == 0) cout << 1 << endl;
    else cout << left + right + 1 << endl;
    
    return 0;
}