【牛客 NC253455】小红走排列 题解（链表+位集合+贪心算法）

本文主要是介绍【牛客 NC253455】小红走排列 题解（链表+位集合+贪心算法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

对于一个排列，小红定义该排列的总消耗为：1走到2，2走到3，……，最终从$n-1$走到$n$所需的最少的总步数。其中，每一步可以向左走一步，也可以向右走一步。

现在，小红只记得排列的大小$n$和走的步数$k$，但不记得排列的构造情况了。请你帮小红还原整个排列。

输入描述

两个正整数$n$和$k$，用空格隔开。

满足条件：$1\le n\le 10^5$ 和 $n-1\le k\le n\ast (n-1)/2$

输出描述

如果无解，请输出-1。

否则输出构造的排列。有多解时输出任意即可。

示例

示例1

输入：

3 2

输出：

1 2 3

说明：

小红从1号开始，向右跳两步即可先跳到2，再跳到3。输出[3,2,1]这个排列也符合要求。

示例2

输入：

4 6

输出：

1 3 4 2

---

思路

使用bitset来存储标记，使用list来存储结果排列。

从输入中读取$n$和$k$，然后计算$j$，$j$是用$k$减去$n-1$的结果，表示除了从每个数字到下一个数字至少需要的步数（即1步）之外，还剩下多少步可以用于调整排列的顺序。

然后对从$n-2$到$1$的每个$i$进行循环，如果剩余的步数$j$大于等于$i$，就将$j$减去$i$，并将$vis[i+2]$标记为已访问。通过贪心算法，尽可能地使用剩余的步数来改变排列的顺序。

定义一个布尔变量dir，用于控制新的元素是添加到排列的前面还是后面。对于从$1$到$n$的每个$i$，如果$vis[i]$被标记为已访问，就反转dir。然后根据dir的值，将$i$添加到排列的前面或后面。

最后，输出排列中的每个元素。这个排列就是问题的一个解。如果有多个解，输出任意一个即可。

输出描述中提到，如果无解，请输出-1。如果给定的步数 k 大于 $n\ast (n-1)/2$ 或小于 $n-1$，那么就无法找到一个排列使得总消耗等于 k，即这个问题无解。但是输入描述中，给定 k 的范围为 $n-1\le k\le n\ast (n-1)/2$，所以无解的情况实际上是不会出现的，不需要特别考虑无解。

---

AC代码

#include <algorithm>
#include <bitset>
#include <iostream>
#include <list>
#define AUTHOR "HEX9CF"
using namespace std;
using ll = long long;const int N = 1e5 + 7;ll n, k;
list<int> li;
bitset<N> vis;int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);li.clear();vis.reset();cin >> n >> k;ll j = k - (n - 1);for (int i = n - 2; i > 0; i--) {if (j >= i) {j -= i;vis[i + 2] = 1;}}bool dir = 0;for (int i = 1; i <= n; i++) {if (vis[i]) {dir ^= 1;}if (dir) {li.push_front(i);} else {li.push_back(i);}}for (const auto i : li) {cout << i << " ";}cout << endl;return 0;
}

这篇关于【牛客 NC253455】小红走排列 题解（链表+位集合+贪心算法）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---