如果一个数列S满足对于所有的合法的i,都有S[i + 1] = S[i] + d, 这里的d也可以是负数和零,我们就称数列S为等差数列。 小易现在有一个长度为n的数列x,小易想把x变为一个等差数列。小易允许在数列上做交换任意两个位置的数值的操作,并且交换操作允许交换多次。但是有些数列通过交换还是不能变成等差数列,小易需要判别一个数列是否能通过交换操作变成等差数列
运行时间： 48 ms 占用内存：9024K
import java.util.Scanner; public class Wangyib { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub /*解题思路：从大到小排序 * 使用那些排序过程中能每一趟都是确定排序位置的算法 * 排序的过程得知数差，进行判断*/ Scanner in = new Scanner(System.in); int count = in.nextInt(); int temp[] = new int[count]; int d,d0=0; for(int i=0;i<count;i++){ temp[i] = in.nextInt(); } //直接选择排序，第一趟确定最大的在首端 /*for(int i=0;i<count-1;i++){ int max = temp[i]; int maxindex = i; for(int j=i+1;j<count;j++){ if(max<temp[j]){ max=temp[j]; maxindex = j; } } if(i != maxindex){ int t = temp[i]; temp[i] = max; temp[maxindex] = t; } if(i==1){ d0 =temp[i-1]-temp[i]; }else if(i>1){ d =temp[i-1]-temp[i]; if(d != d0){ System.out.println("Impossible"); return; } } } if(temp[count-2]-temp[count-1] == d0){ System.out.println("Possible"); }else{ System.out.println("Impossible"); }*/ //冒泡排序，第一趟确定最小的在末端 for(int i=1;i<count;i++){ for(int j=0;j<count-i;j++){ if(temp[j]<temp[j+1]){ int t = temp[j]; temp[j] = temp[j+1]; temp[j+1] = t; } } if(i == 2){ d0 = temp[count-2]-temp[count-1]; }else if(i>2){ d = temp[count-i]-temp[count-i+1]; if(d != d0){ System.out.println("Impossible"); return; } } } if(temp[0]-temp[1] == d0){ System.out.println("Possible"); }else{ System.out.println("Impossible"); } for(int i=0;i<count;i++){ System.out.print(temp[i]+" "); } } }