题目描述
难度分:1600
输入T(≤104)表示T组数据。所有数据的n之和≤2×105。
每组数据输入n(1≤n≤2×105)和k(1≤k≤1012)。
考虑1~n的一个排列p。计算p的所有非空连续子数组的最小值的和,记作S(p)。在所有1~n的排列中,设S(p)的最大值为maxS。
对于所有满足S(p)=maxS的排列p,输出其中字典序第k小的排列p。如果满足S(p)=maxS的排列个数小于k,输出−1。
输入样例
6
3 2
3 3
4 11
4 6
6 39
7 34
输出样例
1 3 2
2 3 1
-1
2 4 3 1
-1
2 3 4 5 7 6 1
算法
贡献法+构造
对于任意一个排列p,利用贡献法,就可以知道1~n作为最小值时,对应子数组对S的贡献(主要考察某个数x作为最小值时,左边界和右边界分别可以延伸多源)。
要想S最大,肯定就希望小的数字贡献小,这样大的数字贡献就会大(因为子数组的总数是确定的)。先考虑1,如果1在1和n两个端点位置,就有n个子数组为答案贡献1;但如果1在中间某个位置x,那就有x×(n−x+1)>n个子数组为S产生1的贡献。这是我们不希望看到的,因此1~n,每次尽量让数字填在两端,除了最后一个n,其他每个数字都有两种填法,因此S=maxS总共有2n−1个排列,如果2n−1<k就无解。
然后l=1,r=n开始填数。如果未填数的排列数<k,就把当前要填的数cur填在r位置,r指针左移;否则将cur填在l位置,l指针右移。注意2n−1是很大的,每填一个数自由度都要除以2,我们只维护指数的变化就可以了,每填一个数指数就减去1。
复杂度分析
时间复杂度
填的数字从1增长到n,且在填数的过程就是双指针算法,左右指针l和r都不会回退,因此时间复杂度为O(n)。
空间复杂度
整个过程中只使用了有限几个变量,额外空间复杂度为O(1)。
C++ 代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 200010;
int t, n, a[N];
LL k;
int main() {
scanf("%d", &t);
while(t--) {
scanf("%d%lld", &n, &k);
bool ok = true;
if(n < 50 && (1LL<<n - 1) < k) ok = false;
if(!ok) {
puts("-1");
}else {
int l = 1, r = n, cur = 1, p = n - 2;
while(p >= 0) {
if(p <= 50 && k > (1LL<<p)) {
a[r--] = cur++;
k -= 1LL<<p;
}else {
a[l++] = cur++;
}
p--;
}
while(cur <= n) {
a[l++] = cur++;
}
for(int i = 1; i <= n; i++) {
printf("%d ", a[i]);
}
puts("");
}
}
return 0;
}