问题：
如果一个数列S满足对于所有的合法的i,都有S[i + 1] = S[i] + d, 这里的d也可以是负数和零,我们就称数列S为等差数列。
小易现在有一个长度为n的数列x,小易想把x变为一个等差数列。小易允许在数列上做交换任意两个位置的数值的操作,并且交换操作允许交换多次。
但是有些数列通过交换还是不能变成等差数列,小易需要判别一个数列是否能通过交换操作变成等差数列
输入描述:
输入包括两行,第一行包含整数n(2 ≤ n ≤ 50),即数列的长度。
第二行n个元素x[i](0 ≤ x[i] ≤ 1000),即数列中的每个整数。
输出描述:
如果可以变成等差数列输出"Possible",否则输出"Impossible"。
输入例子1:
3
3 1 2
输出例子1:
Possible
思路：
先将输入的数组进行排序，判断相邻数组之间的差值，若不完全相同，则说明不是等差。
java程序
public class ArithmeticSequence {
public static void main(String[] args) {
// 输入
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = scanner.nextInt();
}
// 快速排序
sortSmallToBig(arr, 0, arr.length - 1);
// 判断差值
int diff = arr[1] - arr[0];//先将前两个数的差赋给变量diff
for (int i = 2; i < arr.length; i++) {
int temp = arr[i] - arr[i - 1]; //后续相邻整数间的差值赋给temp
if (temp != diff) {//若他们之间的差和前两个差不等，说明不是等差数列，输出Impossible 并结束程序。
System.out.println("Impossible");
return;
}
}
System.out.println("Possible");
}
// smallToBig和sortSmallToBig是快速排序。 针对数组进行从小到大的排序。
// 调用 sortSmallToBig(int[] array, int start, int end) 传入数组 0 和数组.lenth-1.
public static int smallToBig(int[] array, int start, int end) {
int key = array[start];
while (start < end) {
while (array[end] >= key && end > start) {
end--;
}
array[start] = array[end];
while (array[start] <= key && end > start) {
start++;
}
array[end] = array[start];
}
array[end] = key;
return end;
}
public static void sortSmallToBig(int[] array, int start, int end) {
if (start >= end) {
return;
}
int local = smallToBig(array, start, end);
sortSmallToBig(array, start, local - 1);
sortSmallToBig(array, local + 1, end);
}
}
