网站建设网页与数据库连接,抖音小程序怎么做,网页找什么公司维护,什么是电商创业Problem: AcWing 1211. 蚂蚁感冒 文章目录 思路解题方法复杂度Code 思路 这是一个模拟题。题目的意思是#xff0c;如果一只蚂蚁感冒了#xff0c;那么它会把感冒传给所有和它相向而行的蚂蚁。所以我们只需要找出所有和第一只蚂蚁相向而行的蚂蚁就可以了。具体来说#xff0… Problem: AcWing 1211. 蚂蚁感冒 文章目录 思路解题方法复杂度Code 思路 这是一个模拟题。题目的意思是如果一只蚂蚁感冒了那么它会把感冒传给所有和它相向而行的蚂蚁。所以我们只需要找出所有和第一只蚂蚁相向而行的蚂蚁就可以了。具体来说如果第一只蚂蚁向右移动那么所有在它右边且向左移动的蚂蚁都会被感染如果第一只蚂蚁向左移动那么所有在它左边且向右移动的蚂蚁都会被感染。 解题方法 我们首先读入所有蚂蚁的位置和方向。然后我们遍历所有的蚂蚁对于每一只蚂蚁我们判断它是否和第一只蚂蚁相向而行。如果是我们就把它加入到感冒蚂蚁的队列中。最后我们输出感冒蚂蚁的数量。 具体的判断方法是如果第一只蚂蚁向右移动位置为正那么所有在它右边且向左移动的蚂蚁位置为负都会被感染如果第一只蚂蚁向左移动位置为负那么所有在它左边且向右移动的蚂蚁位置为正都会被感染。 复杂度
时间复杂度: O ( n ) O(n) O(n)我们需要遍历所有的蚂蚁。 空间复杂度: O ( n ) 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;}}
