AcWing 1211. 蚂蚁感冒

Problem: AcWing 1211. 蚂蚁感冒

思路

这是一个模拟题。题目的意思是，如果一只蚂蚁感冒了，那么它会把感冒传给所有和它相向而行的蚂蚁。所以我们只需要找出所有和第一只蚂蚁相向而行的蚂蚁就可以了。具体来说，如果第一只蚂蚁向右移动，那么所有在它右边且向左移动的蚂蚁都会被感染；如果第一只蚂蚁向左移动，那么所有在它左边且向右移动的蚂蚁都会被感染。

解题方法

我们首先读入所有蚂蚁的位置和方向。然后我们遍历所有的蚂蚁，对于每一只蚂蚁，我们判断它是否和第一只蚂蚁相向而行。如果是，我们就把它加入到感冒蚂蚁的队列中。最后，我们输出感冒蚂蚁的数量。
具体的判断方法是：如果第一只蚂蚁向右移动（位置为正），那么所有在它右边且向左移动的蚂蚁（位置为负）都会被感染；如果第一只蚂蚁向左移动（位置为负），那么所有在它左边且向右移动的蚂蚁（位置为正）都会被感染。

复杂度

时间复杂度:

$O(n)$，我们需要遍历所有的蚂蚁。

空间复杂度:

$O(n)$，我们需要存储所有蚂蚁的位置和方向。

Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;

public class Main {
	static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
	static StreamTokenizer sr = new StreamTokenizer(in);
	static int MAXN = 60;
	static int[] arr = new int[MAXN];
	static int n;

	public static void main(String[] args) throws IOException {
		n = nextInt();
		for (int i = 0; i < n; i++) {
			arr[i] = nextInt();
		}
		int lr = 0, rl = 0, res = 0;
		for (int i = 0; i < n; i++) {
			if (Math.abs(arr[i]) < Math.abs(arr[0]) && arr[i] > 0)
				lr++;
			else if (Math.abs(arr[i]) > Math.abs(arr[0]) && arr[i] < 0)
				rl++;
		}
		if ((arr[0] < 0 && lr == 0 )|| (arr[0] > 0 && rl == 0)) {
			res = 1;
		} else {
			res = lr + rl + 1;
		}
		out.println(res);
		out.flush();

	}

	private static int nextInt() throws IOException {
		sr.nextToken();
		return (int) sr.nval;
	}

}