小易老师是非常严厉的,它会要求所有学生在进入教室前都排成一列,并且他要求学生按照身高不递减的顺序排列。有一次,n个学生在列队的时候,小易老师正好去卫生间了。学生们终于有机会反击了,于是学生们决定来一次疯狂的队列,他们定义一个队列的疯狂值为每对相邻排列学生身高差的绝对值总和。由于按照身高顺序排列的队列的疯狂值是最小的,他们当然决定按照疯狂值最大的顺序来进行列队。现在给出n个学生的身高,请计算出这些学生列队的最大可能的疯狂值。小易老师回来一定会气得半死。
import java.util.Scanner; public class Wangyig { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub /*解题思路： * 中间最大，再在两边放最小的两个，再放次大的两个 * */ Scanner in = new Scanner(System.in); int n=in.nextInt(); int a[] =new int[n]; int b[] =new int[n];//用来放疯狂队列 int mid = 0,midl,midr,sum=0,fin=0; int small=n-1,big=1; Boolean tag = true; for(int i=0;i<n;i++){ a[i] = in.nextInt(); } //先从大到小排序,直接选择排序 for(int i=0;i<n-1;i++){ int max = a[i]; int maxi = i; for(int j=i+1;j<n;j++){ if(max<a[j]){ max = a[j]; maxi = j; } } if(maxi != i){ int temp = a[i]; a[i] = max; a[maxi] = temp; } } if(n%2 == 0){ mid = n/2-1; }else{ mid = n/2; } b[mid] = a[0]; midl = mid-1; midr = mid+1; while(midl>=0 || midr<n){ if(tag == true){ if(midr<n){ b[midr++]=a[small--]; System.out.println("a"+b[midr-1]); } if(midl>=0){ b[midl--]=a[small--]; System.out.println("b"+b[midl+1]); } tag = false; }else{ if(midr<n){ b[midr++]=a[big++]; System.out.println("c"+b[midr-1]); } if(midl>=0){ b[midl--]=a[big++]; System.out.println("d"+b[midl+1]); } tag = true; } } for(int i=0;i<n-1;i++){ System.out.println(b[i]); sum+=Math.abs(b[i]-b[i+1]); } b[mid] = a[n-1]; midl = mid-1; midr = mid+1; small=n-2;big=0; tag = true; System.out.println("~~~~~~~~~~~~~~~~~~"); while(midl>=0 || midr<n){ if(tag == true){ if(midr<n){ b[midr++]=a[big++]; System.out.println("c"+b[midr-1]); } if(midl>=0){ b[midl--]=a[big++]; System.out.println("d"+b[midl+1]); } tag = false; }else{ if(midr<n){ b[midr++]=a[small--]; System.out.println("a"+b[midr-1]); } if(midl>=0){ b[midl--]=a[small--]; System.out.println("b"+b[midl+1]); } tag = true; } } for(int i=0;i<n-1;i++){ System.out.println(b[i]); fin+=Math.abs(b[i]-b[i+1]); } fin=fin>sum?fin:sum; System.out.print(b[n-1]+" "+fin); } }