蓝桥杯——数字游戏

问题描述
　　给定一个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

一个 1 ~ N 的整数数列，在特定的排列下相邻数两两相加得到一行新的整数数列，重复两两相加操作，最终得到一个数。显然，我们需要知道 1 ~ N 的所有的排列，即一个数列的全排列。

如何求出一个序列的全排列呢？C++的STL为我们提供了一个十分有用的函数：next_permutation。它能够按照字典序从小到大生成一个序列的全排列，只需要传入这个序列的起始和结束位置即可。注意：使用next_permutation求全排列时，需要首先对数列进行从小到大的排序。

#include 
#include  
#include 
#include  
using namespace std;
int main() {
	vector range {1,2,3,4};
	do {
		// 具体操作
	}while(next_permutation(begin(range), end(range)));
	return 0;
}

在知道序列的所有排列后，对每个排列都进行两两相加，看看最终的结果是否等于输入的和。由于next_permutation求得的序列是从小到大，所以第一个找到的符合条件的序列就是字典序最小的序列，直接输出即可。

#include 
using namespace std;

int main() {
	int n, sum;
	cin >> n >> sum;
	
	int* number_1 = new int[n + 1]();
	for(int i=1; i<=n; i++) {
		number_1[i] = i;
	}
	
	int** number_2 = new int*[n + 1]();
	for(int i=1; i<=n; i++) {
		number_2[i] = new int[n + 1]();
	}
	
	do {
		for(int i=1; i<=n; i++) {
			number_2[1][i] = number_1[i];
		}
		
		for(int i=2; i<=n; i++) {
			for(int j=1; j<=n-i+1; j++) {
				number_2[i][j] = number_2[i-1][j] + number_2[i-1][j+1];
			}
		}
		
		if(sum == number_2[n][1]) {
			for(int i=1; i<=n; i++) {
				cout << number_2[1][i] << " ";
			}
			cout << endl;
			break;
		}
	} while(next_permutation(number_1 + 1, number_1 + n + 1));
	
	delete[] number_1;
	for(int i=1; i<=n; i++) delete[] number_2[i];
	delete[] number_2;
	return 0;
}