1. 问题描述:
给定一个长度为 n 的整数序列 a1,a2,…,an。请你对序列进行重新排序(也可以保持原序列),要求新序列满足每个元素(第 1 个除外)都恰好是前一个元素的两倍或前一个元素的三分之一。保证输入一定有解。
输入格式
第一行包含整数 n。第二行包含 n 个整数 a1,a2,…,an。
输出格式
一行 n 个整数,表示排序后的序列。输出任意合法方案即可。
数据范围
前三个测试点满足 2 ≤ n ≤ 10。
所有测试点满足 2 ≤ n ≤ 100,1 ≤ ai ≤ 3 × 10 ^ 18。
输入样例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
来源:https://www.acwing.com/problem/content/description/4214/
2. 思路分析:
这道题目属于典型的思维题,一般思维题都需要挖掘一下题目存在什么性质,因为题目规定了有解所以我们只需要考虑有解的序列即可,由于涉及到2的倍数和3的倍数所以我们可以用xi表示第i个数因子2的数量,yi表示第i个数因子3的数量,对于一个合法的序列我们需要考虑一下需要满足什么样的性质,先考虑因子2,因为当前的数字要么是前一个数字的2倍要么是前一个数的1/3所以当前数字因子2的数量要么比前一个数的因子2的数量多1,要么相等,如果当前数字是前一个数字的1/3那么此时因子2的数量是相等的,因子3的数量前一个数比后一个数多1,所以一个解是合法序列需要满足的必要条件(一般是看一下解满足的必要条件然后判断是否可以证明出来是充分条件如果不是唯充分条件那么看必要条件是否是唯一的):
- xi < x(i + 1) 或者 xi = x(i + 1) 并且yi > y(i + 1)
那么会不会存在有两个数的因子2的数量等于因子3的数量呢?也即xi = x(i + 1)并且yi = y(i + 1),可以证明是不存在这两个数字的,如果xi = xj,若i与j之间存在其他的数则xi = x(i + 1) = x(i + 2)... = xj,根据上面的合法序列满足的必要条件可以知道yi > y(i + 1) > y(i + 2) > ... yj,所以与yi = y(i + 1) = y(i + 2) = ... yj是矛盾的所以x与y是不可能同时相等的,所以满足上面必要条件的序列是唯一的,如果只是满足了必要条件那么可能不是一个合法序列但是满足这个必要条件的序列是唯一的所以这个合法序列也是唯一的,可以发现满足必要条件的序列类似于c++中pair的双关键字排序,所以我们可以按照因子2的数量升序排序,因子3的数量降序排序,最终得到的排序序列就是唯一的合法序列(一个解需要满足的条件是必要条件,能够推出解的是充分条件)。
3. 代码如下:
class Solution:
# 计算x有多少个因子b
def get(self, x: int, b: int):
# 一直除就可以
res = 0
while x % b == 0:
x //= b
res += 1
return res
def process(self):
n = int(input())
a = list(map(int, input().split()))
q = list()
for x in a:
q.append((self.get(x, 2), -self.get(x, 3), x))
# 按照双关键字排序: 因子2的数量升序排列, 因子3的数量降序排序
q.sort(key=lambda x: (x[0], x[1]))
for i in range(n):
print(q[i][2], end=" ")
if __name__ == '__main__':
Solution().process()