证明
- 首先这题一个
破局的关键就是不能去思考碰头换方向去搜索答案
,因为复杂度太高,我们可以理解为是穿越对方,不会回头,而感冒就是穿过的副产物。这样就可以直接分析答案。 - 然后我们去思考一个if—else的判断逻辑:
如果感冒蚂蚁向右走:
它右侧的所有向左走的蚂蚁必然感染,而向右的不会感染;
它左边向左走的蚂蚁一定不会感染,而左边向右走的蚂蚁则取决于它右侧有没有向左走的蚂蚁,有的话必定会被感染,没有的话则不会被感染。
发现关键在于右边向左走的蚂蚁,和左边向右走的蚂蚁数量
设它右边向左走的蚂蚁为right
,左边向右走的为left
如果感冒蚂蚁向左走则完全相反
合并
当a[0] > 0 向右走
if right > 0 ——》 res = left + right + 1
if right = 0 ——》 res = 1
当a[0] < 0 向左走
if left > 0 ——》 res = left + right + 1
if left = 0 ——》 res = 1
代码
import java.io.*;
public class Main {
static int n, left, right, N = 110;
static int a[] = new int [N];
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
public static void main(String [] args) throws IOException{
n = Integer.parseInt(br.readLine());
String s[] = br.readLine().split(" ");
for(int i=0; i<n; i++) a[i] = Integer.parseInt(s[i]);
for(int i=1; i<n; i++){
// 右边向左走的
if(Math.abs(a[i]) > Math.abs(a[0]) && a[i] < 0) right ++;
// 左边向右走的
if(Math.abs(a[i]) < Math.abs(a[0]) && a[i] > 0) left ++;
}
if((a[0] > 0 && right == 0) || (a[0] < 0 && left == 0))
System.out.println(1);
else
System.out.println(left + right + 1);
}
}