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

一、问题描述

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

二、问题简析

这道题的关键是如何处理蚂蚁掉头的问题。我们可以把蚂蚁掉头看作直接穿了过去。

为什么可以这样做？如果两只蚂蚁中有一只感染，则碰头后两只都感染了，不需要区分哪一只。如果两只蚂蚁都没感染，则碰头后仍未感染，也不需要区分哪一只。
这样做以后，不再需要考虑掉头，每只蚂蚁只需要朝初始方向前进，期间碰到感染的蚂蚁则染病。

值得注意的是，因为蚂蚁的速度都是一样的，所以碰头只可能发生在相向的蚂蚁之间，同向的蚂蚁永远也不可能碰头。因此，感染只需要考虑相向的蚂蚁。

先根据 $X_i$ 的绝对值，按升序排序，得到蚂蚁在杆子上的位置。
因为初始感染的蚂蚁只要一只，同时只要相向而行的蚂蚁才会被感染，所以，无论初始感染蚂蚁的方向如何，在其左边的蚂蚁，只有朝右（$>0$）才会感染；在其右边的蚂蚁，只有朝左（$<0$）才会感染。（解释：初始感染蚂蚁向左运动，先感染左边的蚂蚁，再由左边的蚂蚁感染右边的蚂蚁；向右运动，先感染右边的蚂蚁，再由右边的蚂蚁感染左边的蚂蚁。）
需要注意几种特殊情况，此时，只有一只蚂蚁感染：

• 1、初始感染蚂蚁向左，且其左边的蚂蚁没有一只向右，即左边无感染，则右边也不会有蚂蚁感染。
• 2、初始感染蚂蚁向右，且其右边的蚂蚁没有一只向左，即右边无感染，则左边也不会有蚂蚁感染。

三、AC代码

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int quickin(void)
{
	int ret = 0;
	bool flag = false;
	char ch = getchar();
	while (ch < '0' || ch > '9')
	{
		if (ch == '-')    flag = true;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9' && ch != EOF)
	{
		ret = ret * 10 + ch - '0';
		ch = getchar();
	}
	if (flag)    ret = -ret;
	return ret;
}

int A[55], n, B;

bool cmp(const int &a, const int &b)
{
	return abs(a) < abs(b);
}

int main()
{
	#ifdef LOCAL
	freopen("test.in", "r", stdin);
	#endif
	
	n = quickin();
	for (int i = 0; i < n; i++)
		A[i] = quickin();
	B = A[0];
	sort(A, A + n, cmp);
	
	int i, t1 = 0, t2 = 0;
	for (i = 0; A[i] != B; i++)
	{
		if (A[i] > 0)
			t1 +=1;
	}
	for (i += 1; i < n; i++)
	{
		if (A[i] < 0)
			t2 += 1;
	}
	
	if (B > 0 && t2 == 0)
	{
		cout << 1 << endl;
		return 0;
	}
	if (B < 0 && t1 == 0)
	{
		cout << 1 << endl;
		return 0;
	}
	
	cout << t1 + t2 + 1 << endl;
	
	return 0;
}

完