本题解同步更新于我的博客欢迎围观★,°:.☆(￣▽￣)/$:.°★ 。

题意描述

构造一个$11$到$nn$的排列，使得其中正好有$kk$个二元组$(i,j)(i,\; j)$满足，$1\le i<j\le n1\backslash le\; i\backslash lt\; j\backslash le\; n$ && $a_i-a_j=2^x(x\in N)a\_i\; -\; a\_j\; =\; 2^x(x\backslash in\; N)$

$(1\le n\le 10^6,1\le k\le 10^9)(1\backslash le\; n\; \backslash le\; 10^6,\; 1\backslash le\; k\; \backslash le\; 10^9)$

做法分析

首先我们可以发现，每个数，它在序列能构成有用二元组的只有比他大的，那也就是说我们找到了排列的二元组最多情况，也就是$nn$到$11$按从大到小顺序排列。

那进一步想，每个数在序列中最大能对他有用的数（即能构成二元组的）有多少个呢，发现对于每个数$ii$，满足$i+2^x\le ni+2^x\backslash le\; n$的最大的$xx$再$+1+1$即为每个数的最大贡献，其实也就是${}_2(n-i)+1\backslash log\_2(\; \{n\; -\; i\}\; )+\; 1$。

这样就有了构造方法，对于每个不是$nn$(没有比$nn$大的数了)的数$ii$，如果${}_2(n-i)+1\le k\backslash log\_2(\; \{n\; -\; i\}\; )+\; 1\backslash le\; k$，那就将$kk$减去其贡献值，并把他放到最后。

举个例子：

输入：5 5 得到：3 4 5 2 1

从$11$开始，他的贡献最大是${}_2(5-1)+1=3\backslash log\_2(\; \{5\; -\; 1\}\; )+\; 1\; =\; 3$，可以与$2,3,52,3,5$形成二元组，小于$kk$，于是$kk$减$33$，标记一下$11$被放到后面了。

再到$22$，贡献是${}_2(5-2)+1=2\backslash log\_2(\; \{5\; -\; 2\}\; )+\; 1\; =\; 2$，可以与$3,43,4$形成二元组，小于等于$kk$，于是$kk$减$22$，标记一下$22$被放到后面了，这时候$kk$已经等于$00$了，即我们构造的排列已经符合要求。

这样应该就很清楚了,时间复杂度$O(n)O(n)$。

点个赞再走呗/kel

代码

#include <bits/stdc++.h>
using namespace std;

int n, k;
int flag1[1000010], flag2[1000010];
int lg[1000010];
int main()
{
    scanf("%d%d", &n, &k);
    for(int i = 2; i <= n; i++)
        lg[i] = lg[i >> 1] + 1;
    for(int i = 1; i <= n; i++)
        flag1[i] = 1;
    for(int i = 1; i < n; i++)
    {
        int cha = n - i;
        if(lg[cha] + 1 <= k)
        {
            flag1[i] = 0;
            flag2[i] = 1;
            k -= lg[cha] + 1;
        }
        if(k == 0)
            break;
    }
    if(k > 0)
    {
        printf("-1");
        return 0;
    }
    for(int i = 1; i <= n; i++)
        if(flag1[i])
            printf("%d ", i);
    for(int i = n; i >= 1; i--)
        if(flag2[i])
            printf("%d ", i);
    
    return 0;
}