AcWing 4211. 序列重排

题目描述
给定一个长度为 n 的整数序列 a1,a2,…,an。
请你对序列进行重新排序（也可以保持原序列），要求新序列满足每个元素（第 1 个除外）都恰好是前一个元素的两倍或前一个元素的三分之一。
保证输入一定有解。

输入格式
第一行包含整数 n。
第二行包含 n 个整数 a1,a2,…,an。

输出格式
一行 n 个整数，表示排序后的序列。输出任意合法方案即可。

数据范围
前三个测试点满足 2≤n≤10。
所有测试点满足 2≤n≤100，1≤ai≤3×10¹⁸ 。

输入样例1：

6
4 8 6 3 12 9

输出样例1：

9 3 6 12 4 8

输入样例2：

4
42 28 84 126

输出样例2：

126 42 84 28

输入样例3：

2
1000000000000000000 3000000000000000000

输出样例3：

3000000000000000000 1000000000000000000

解题思路
用list存储输出序列，方便头插和尾插（就是就是我需要一条可以两头长的大长虫 ）
输入一定有解，所以每个数在输出序列中肯定有他自己的位置，所以我们大可以从第一个数开始找起
设tmpb记序列头，tmpe存序列尾
有尾的2倍或1/3的数据，且未访问过就push_back();
有头的1/2或3倍的数据，且未访问过就push_front();
当list长度与输入序列长度相同时，就说明我们找到解啦，啦啦啦啦

然后需要说明的关键的一个事就是给定序列中某个数的2倍或1/3其实是不会同时出现的，也就是解是唯一的（下面题解说明），所以一趟就能确定序列

代码1

#include<iostream>
#include<algorithm>
#include<list>
using namespace std;
long long arr[100];
list<long long> li;
int visited[100];
int main() {
	int n;
	cin >> n;
	int num = 1;
	for (int i = 0; i < n; ++i) {
		cin >> arr[i];
	}
	visited[0] = 1;
	li.push_back(arr[0]);
	long long tmpb = arr[0], tmpe = arr[0]; //头、尾数据
	while (num != n) {
		int index = find(arr, arr + n, tmpe * 2) - arr;
		if (visited[index] != 1 && index != n) {
			li.push_back(arr[index]);
			visited[index] = 1;
			tmpe *= 2;
			num++;
		}
		else if (tmpe % 3 == 0) {
			index = find(arr, arr + n, tmpe / 3) - arr;
			if (visited[index] != 1 && index != n) {
				li.push_back(arr[index]);
				visited[index] = 1;
				tmpe /= 3;
				num++;
			}

		}
		index = find(arr, arr + n, tmpb * 3) - arr;
		if (visited[index] != 1 && index != n) {
			li.push_front(arr[index]);
			visited[index] = 1;
			tmpb *= 3;
			num++;
		}
		else if (tmpe % 2 == 0) {
			index = find(arr, arr + n, tmpb / 2) - arr;
			if (visited[index] != 1 && index != n) {
				li.push_front(arr[index]);
				visited[index] = 1;
				tmpb /= 2;
				num++;
			}
		}
	}
	while (!li.empty()) {
		cout << li.front() << " ";
		li.pop_front();
	}
	return 0;
}

官方题解思路
双关键字排序
https://www.acwing.com/video/3668/
在这里插入图片描述
设ai的因子2的个数为xi，因子3的个数为yi；

每个元素都恰好是前一个元素的两倍或三分之一
则，输出序列B满足必要条件A：x(i+1)>xi且y(i+1)=yi或者x(i+1)=xi且y(i+1)<yi（B->A）

满足必要条件的序列唯一，如图：
在这里插入图片描述
然后捏，解一定满足必要条件，而满足必要条件的序列又唯一，所以满足必要条件就能推出解（A->B），所以A是B的充要条件，就能拿去解题啦

代码2_1

#include<iostream>
#include<algorithm>
using namespace std;
struct Arr {
	long long num;
	int x = 0; //因子2个数
	int y = 0; //因子3个数
}arr[100];
bool cmp(Arr a, Arr b) {
	if (a.x == b.x) {
		return b.y < a.y;
	}
	return a.x < b.x;
}
int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> arr[i].num;
		long long tmp = arr[i].num;
		while (tmp % 2 == 0) {
			arr[i].x++;
			tmp /= 2;
		}
		while (tmp % 3 == 0) {
			arr[i].y++;
			tmp /= 3;
		}
	}
	sort(arr, arr + n, cmp);
	for (int i = 0; i < n; ++i) {
		cout << arr[i].num << " ";
	}
}

又因为，增-减=增，所以也可以用rank=x-y代替x和y作为排序依据

代码2_2

#include<iostream>
#include<algorithm>
using namespace std;
struct Arr {
	long long num;
	int rank = 0;
}arr[100];
bool cmp(Arr a, Arr b) {
	return a.rank < b.rank;
}
int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> arr[i].num;
		long long tmp = arr[i].num;
		while (tmp % 2 == 0) {
			arr[i].rank++;
			tmp /= 2;
		}
		while (tmp % 3 == 0) {
			arr[i].rank--;
			tmp /= 3;
		}
	}
	sort(arr, arr + n,cmp);
	for (int i = 0; i < n; ++i) {
		cout << arr[i].num << " ";
	}
}