AcWing 1211. 蚂蚁感冒
原题链接
简单
作者:
Gabriel.
,
2024-11-03 20:38:42
,
所有人可见
,
阅读 8
突破口
1.蚂蚁碰头后分别反向,等价于都不反向,直接穿过
,按原来的路线走,只是若碰头的蚂蚁有一只感冒,则碰头后两只蚂蚁都感冒
2.以最开始感冒的蚂蚁为界限,分类讨论一共会造成多少只蚂蚁感冒
:
1️⃣若最开始感冒的蚂蚁往右走,则其右端往右走的蚂蚁一定不会感冒(不会相遇);其右端往左走的蚂蚁一定感冒(一定相遇);其左端往左走的蚂蚁一定不会感冒(不会相遇);若其右端存在往左走的蚂蚁,则其左端往右走的蚂蚁一定感冒(一定相遇),反之则不会感冒。
2️⃣⃣若最开始感冒的蚂蚁往左走,则其左端往左走的蚂蚁一定不会感冒(不会相遇);其左端往右走的蚂蚁一定感冒(一定相遇);其右端往右走的蚂蚁一定不会感冒(不会相遇);若其左端存在往右走的蚂蚁,则其右端往左走的蚂蚁一定感冒(一定相遇),反之则不会感冒。
代码
#include <bits/stdc++.h>
using namespace std;
int n;
int st[55];
int res = 1;
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &st[i]);
int tmp = st[1];
if (tmp > 0)
{
for (int i = 2; i <= n; i++)
if (st[i] < -tmp)
res++;
if (res!=1)
for (int i = 2; i <= n; i++)
if (st[i] > 0 && st[i] < tmp)
res++;
}
else
{
for (int i = 2; i <= n; i++)
if (st[i] > 0 && st[i] < -tmp)
res++;
if (res!=1)
for (int i = 2; i <= n; i++)
if (st[i] < tmp)
res++;
}
printf("%d", res);
return 0;
}