重生之花开富贵,九阴真经情报之争,张艳奕
原创
注意,用户输入的数据是乱序的,首先将用户输出的数据按绝对值大小升序排序;
题目中的前进速度1厘米/秒不必理会,蚂蚁看上去是动态的,实则可以视为静态;
离开杆子的蚂蚁是绝对不会和杆子上其他蚂蚁相撞的,其存在与否无关紧要。
只有相邻的蚂蚁才有机会相撞,并且只可能和面前的蚂蚁相撞,和其背后的蚂蚁
是不可能相撞的。所以,我们可以循环扫描蚂蚁数组,判断哪两只蚂蚁会相撞,
相撞则掉头,再在此基础上判断两只蚂蚁中是否存在只有一个蚂蚁感冒,存在则
感冒蚂蚁数+1,直到数组中所有蚂蚁都不会相撞。
1 import java.util.*; 2 3 public class 蚂蚁感冒 { 4 static int arr[]; 5 static int flag[]; //flag[i]=1代表蚂蚁arr[i]感冒 6 static int n=0; 7 static int total=1; 8 static int ff=0; //ff==1表示蚂蚁已经不会相撞 9 10 /* 11 循环扫描数组,判断相邻两只蚂蚁; 12 相撞则掉头,在此基础上判断两只蚂蚁中是否存在感冒蚂蚁; 13 不相撞继续判断下一组相邻的蚂蚁; 14 直到全部蚂蚁都不会相撞。 15 */ 16 17 static void Ants() { 18 int i=0; 19 while(true) { 20 ff=1; 21 for(i=0;i<=n-1;i++) { 22 if(i!=n-1) { 23 if( arr[i]>0 && arr[i+1]<0 ) { 24 ff=0; 25 arr[i]=arr[i]*-1; 26 arr[i+1]=arr[i+1]*-1; //掉头 27 if( (flag[i]==1 && flag[i+1]!=1) || (flag[i]!=1 && flag[i+1]==1) ) { //有蚂蚁感冒 28 total++; 29 flag[i]=1; 30 flag[i+1]=1; 31 } 32 } 33 } 34 } 35 if(ff==1) { //所有蚂蚁不会相撞 36 System.out.println(total); 37 break; 38 } 39 } 40 } 41 42 static int YiKuan(int left,int right) { //一趟快速排序 43 int x=0; 44 x=arr[left]; 45 while(left<right) { 46 while(left<right && Math.abs(arr[right])>Math.abs(x)) { 47 right--; 48 } 49 if(left<right) { 50 arr[left]=arr[right]; 51 left++; 52 } 53 while(left<right && Math.abs(arr[left])<Math.abs(x)) { 54 left++; 55 } 56 if(left<right) { 57 arr[right]=arr[left]; 58 right--; 59 } 60 } 61 arr[left]=x; 62 return left; 63 } 64 65 static void Quan(int left,int right) { //快速排序 66 if(left<right) { 67 int mid=0; 68 mid=YiKuan(left,right); 69 Quan(left,mid-1); 70 Quan(mid+1,right); 71 } 72 } 73 74 public static void main(String args[]) { 75 Scanner reader=new Scanner(System.in); 76 n=reader.nextInt(); 77 arr=new int[100]; 78 flag=new int[100]; 79 int i=0; 80 for(i=0;i<=n-1;i++) { 81 arr[i]=reader.nextInt(); 82 flag[i]=0; 83 } 84 int x=0; 85 x=arr[0]; //存储首只感冒蚂蚁的值 86 Quan(0,n-1); //快速排序 87 for(i=0;i<=n-1;i++) { 88 if(x==arr[i]) { 89 flag[i]=1; 90 break; 91 } 92 } 93 94 Ants(); 95 } 96 }
(ACCEPT)
13:07:20
2018-06-14
如对本文有疑问,请在下面进行留言讨论,广大热心网友会与你互动!! 点击进行留言回复
浅析我对 String、StringBuilder、StringBuffer 的理解
使用IDEA搭建SSM框架的详细教程(spring + springMVC +MyBatis)
Springboot整合freemarker 404问题解决方案
引入mybatis-plus报 Invalid bound statement错误问题的解决方法
网友评论