题目

资源限制
时间限制：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;
	}
}