问题描述
给定一个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
解题思路:
欲求最初的序列,并且是符合条件的最小序列。可以将所求序列全排列,当每排好一种情况时,则进行累加求和,为了不改变原始数组中的值,需要拷贝一个数组,判断累加和是否等于题给出的和,满足时输出该数组并退出即可。
全排列问题:
全排列问题https://blog.csdn.net/weixin_48898946/article/details/121589155
注意在拷贝数组时,不能用list,因为用list涉及到list的替换元素(set方法),而初始时,list中为空,第一次替换会下标越界(事实上,即使提前处理使得不越界也会超时)。而如果每次都开一个list,对时间和空间都会产生很大代价。由于第五个测试点没有符合条件的解,意味着需要将所有全排列的数都每次开list,所以会超时。所以拷贝数组用一个常规一维数组就行。
java代码:
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] split = br.readLine().split(" ");
int n = Integer.parseInt(split[0]);
int sum = Integer.parseInt(split[1]);
Temp228 temp = new Temp228(n, sum);
temp.dfs(1);
}
}
class Temp228{
int n;
int sum;
boolean visited[];//标志数字是否出现过,避免重复出现
List<Integer> list = new ArrayList<>();//存放实时数据
int []arr;//便于筛选时的拷贝数组
public Temp228(int n, int sum) {
this.n = n;
this.sum = sum;
visited = new boolean[n + 1];
arr = new int[n];
}
public void dfs(int step) {
if(step > n) {
if(compare()) {//当都排列好时,就进行符合条件的筛选
System.exit(0);//选好直接退出程序
}
return;
}
for(int i = 1; i <= n; i++) {
if(!visited[i]) {
visited[i] = true;
list.add(i);
dfs(step + 1);
visited[i] = false;//回溯
list.remove(list.size() - 1);
}
}
}
public boolean compare() {
for(int i = 0; i < list.size(); i++) {
arr[i] = list.get(i);//拷贝数据
}
for(int i = 1; i < n; i++) {//计算相加后的“左下角”值
for(int j = 1; j <= n - i; j++) {
arr[j - 1] = arr[j] + arr[j - 1];
}
}
if(arr[0] == sum) {//符合条件时,直接打印并返回true
for(int i = 0; i < list.size() - 1; i++) {
System.out.print(list.get(i) + " ");
}
System.out.print(list.get(list.size() - 1));
return true;
}
return false;
}
}
提交截图:
版权声明:本文为weixin_48898946原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接和本声明。