文章目錄
- 題目
- 決議
- 代碼
題目
資源限制
時間限制：1.0s 記憶體限制：256.0MB
問題描述
給定一個1～N的排列a[i]，每次將相鄰兩個數相加，得到新序列，再對新序列重復這樣的操作，顯然每次得到的序列都比上一次的序列長度少1，最終只剩一個數字，
例如:
3 1 2 4
4 3 6
7 9
16
現在如果知道N和最后得到的數字sum，請求出最初序列a[i]，為1～N的一個排列，若有多種答案，則輸出字典序最小的那一個，資料保證有解，
輸入格式
第1行為兩個正整數n，sum
輸出格式
一個1～N的一個排列
樣例輸入
4 16
樣例輸出
3 1 2 4
資料規模和約定
0<n<=10
決議
直接通過全排列暴力搜索，由于Java中沒有提供全排列函式 next_permutation，所以要自己實作，注意實作全排列的時候的每個排列之間要滿足升序，從而貪心的達到結果的字典序最小，
代碼
// 數字游戲
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int sum = scanner.nextInt();
int array[] = new int[n];
for (int i=0; i<n; i++) {
array[i] = i+1;
}
do {
int temp[] = new int[n];
System.arraycopy(array, 0, temp, 0, array.length);
// 計算每次生成的排列的最后得到的數字
for(int i=0; i<temp.length-1; i++) {
for(int j=0; j<temp.length-i-1; j++) {
temp[j] = temp[j] + temp[j+1];
}
}
// 如果最后得到的數字等于sum，則輸出結果
if (temp[0] == sum) {
for (int i=0; i<array.length; i++) {
System.out.print(array[i] + " ");
}
break;
}
} while(next_permutation(array));
scanner.close();
}
public static boolean next_permutation(int[] array) {
if(array.length <= 1) {
return false;
}
int i = array.length-2;
// 尋找第一個不滿足降序的數
while (i>=0 && array[i]>array[i+1]) {
i--;
}
if (i == -1) {
return false;
}
// 尋找大于 array[i] 的最小的數，作交換
int j = i + 1;
while (j<array.length && array[j]>array[i]) {
j++;
}
swap(array, i, j-1);
// 對 i 后的數排序
Arrays.sort(array, i+1, array.length);
return true;
}
public static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/394082.html
標籤：其他
上一篇：pygame zero 特訓 - 匯入圖片篇 - （1）
下一篇：猜單詞游戲