原题链接
自己一开始的想法。先根据第一只蚂蚁的方向开始判断,只要相邻的两个数是逆序数对,就会多一只蚂蚁感冒。并且对该方向的后者进行反向处理,之前的蚂蚁不需要再管,继续判断这个后者与此方向后面的蚂蚁是否为逆序数对。当此方向有蚂蚁被感染时,第一只的蚂蚁才会反向,此后另一个方向的蚂蚁才有被感染的可能。
import java.util.Scanner;
class Main{
static int[] arr = new int[101];//因为只有100cm,所以只需要开一个数组来记录蚂蚁所在的位置
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(),index;
//以下是记录第一个感冒的蚂蚁的位置和方向
if((index=sc.nextInt())>0) arr[index]=1;
else arr[Math.abs(index)]=-1;
int startAntPlace = Math.abs(index);
while(--n>0) {//因为第一个蚂蚁已经被记录了,所以是--n而不是n--。下面是记录其他位置的蚂蚁的方向
if((index=sc.nextInt())>0) arr[index]=1;//1表示向右
else arr[Math.abs(index)]=-1;//-1表示向左,0表示没有蚂蚁
}
System.out.println(ff(startAntPlace));
}
public static int ff(int begin) {
int result=1;
if(arr[begin]<0) {
result+=left(begin);
if(result>1) {arr[begin]=fanzhuan(arr[begin]);result+=right(begin);}
}
else {
result+=right(begin);
if(result>1) {arr[begin]=fanzhuan(arr[begin]);result+=left(begin);}
}
return result;
}
public static int left(int begin) {
int result=0,a=0,b=0;
for(int i=begin;i>0;i--) {
if(arr[i]==0)continue;
else{
a=b;
b=arr[i];
}
if((a+b)==0) {
result++;
b=fanzhuan(b);
}
}
return result;
}
public static int right(int begin) {
int result=0,a=0,b=0;
for(int i=begin;i<100;i++) {
if(arr[i]==0)continue;
else{
a=b;
b=arr[i];
}
if((a+b)==0) {
result++;
b=fanzhuan(b);
}
}
return result;
}
public static int fanzhuan(int b) {
if(b==1)return -1;
else return 1;
}
}
后来看了TonyJam的提示,思路豁然开朗。即两只蚂蚁相撞掉头可以看作是一只蚂蚁穿过了另一只蚂蚁,因为相撞之后两只蚂蚁都感冒了,掉不掉头其实无所谓,毕竟都感冒了因此最终的结果就是第一只蚂蚁左边的位置向右走的蚂蚁的数量+第一只蚂蚁右边的位置向左走的蚂蚁的数量+1.当然有两种特殊情况,如果蚂蚁一开始向左走,且左边没有蚂蚁被感染,那么右边的蚂蚁永远不会被感染。如果蚂蚁一开始想右走,且右边没有蚂蚁被感染,那么左边的蚂蚁永远不会被感染。
import java.util.Scanner;
class Main{
static int[] arr = new int[101];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(),index;
if((index=sc.nextInt())>0) arr[index]=1;
else arr[Math.abs(index)]=-1;
int startAntPlace = Math.abs(index);
while(--n>0) {
if((index=sc.nextInt())>0) arr[index]=1;
else arr[Math.abs(index)]=-1;
}
System.out.println(f(startAntPlace));
}
public static int f(int begin) {
int result=1,left=0,right=0;
for(int i=1;i<begin;i++) {
if(arr[i]>0)left++;
}
for(int i=100;i>begin;i--) {
if(arr[i]<0)right++;
}
if(arr[begin]>0&&right==0)return result;
if(arr[begin]<0&&left==0)return result;
else return result+left+right;
}
}