IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> AcWing 4211. 序列重排 -> 正文阅读

[数据结构与算法]AcWing 4211. 序列重排

AcWing 4211. 序列重排

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

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

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

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

输入样例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 << " ";
	}
}

吧啦吧啦
由于这个题的数据比较少哈,莫得什么算法,所以大家dfs啊,模拟啊,找下逻辑关系啥的哈,能做出来就可 T_T。

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-01-17 11:44:21  更:2022-01-17 11:45:57 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年3日历 -2024/3/29 10:05:50-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码