AcWing 1211. 蚂蚁感冒
原题链接
简单
作者:
BLADE_9
,
2023-08-08 19:41:51
,
所有人可见
,
阅读 86
蚂蚁感冒
分析过程
- 掉头问题。本质上没有变,还是一个蚂蚁向左,一个向右,从这个角度可知,必定能走到两端。并且要清楚,掉头不影响感染感冒的分析(如何解释?)。
- 分类统计。以感冒蚂蚁向右爬为例,将所有蚂蚁分类成四种,分别是初始状态下,1、在感冒蚂蚁右边,向左爬;2、在感冒蚂蚁右边,向右爬;3、在感冒蚂蚁左边,向左爬;4、在感冒蚂蚁左边,向右爬。其中1必定感冒,2必定不感冒,3必定不感冒,4在存在1的情况下才会感冒。
实现要点
根据快排思想,在ant数组中,将感冒蚂蚁右边位置的蚂蚁排在其下标的右边,左边位置的蚂蚁排在其下标左边。
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 51;
int ant[N]; // 读取蚂蚁的位置,其中ant[1]为感冒蚂蚁
int n;
int qsort(int a[N]) {
// for (int i = 1; i <= n; i++) cout << a[i] << ' ';
a[0] = a[1];
int l = 1, r = n;
while (l < r) {
while (abs(a[r]) >= abs(a[0]) && l < r) r--;
if (l < r) a[l] = a[r];
while (abs(a[l]) <= abs(a[0]) && l < r) l++;
if (l < r) a[r] = a[l];
}
a[l] = a[0];
// cout << l << endl;
// for (int i = 1; i <= n; i++) cout << a[i] << ' ';
return l;
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> ant[i];
}
int pos = qsort(ant);
int res = 1;
int flag = false;
if (ant[pos] > 0) { // 感冒蚂蚁向右
for (int i = pos + 1; i <= n; i++) {
if (ant[i] < 0) {
// 右边向左的必感染
res++;
flag = true;
}
}
for (int i = 1; i < pos; i++) {
// 左边向右的,当右边有向左时必感染
if (ant[i] > 0) {
if (flag)
res++;
}
}
}
else { // 感冒蚂蚁向左
for (int i = 1; i < pos; i++) {
//左边向右的必感染
if (ant[i] > 0) {
res++;
flag = true;
}
}
for (int i = pos + 1; i <= n; i++) {
if (ant[i] < 0)
if (flag)
res++;
}
}
cout << res << endl;
return 0;
}