传送门

分析

1.容易发现的一件事，当n,n-1,n-2......2,1排列时是满足条件的（i，j）对最多的n排列

2.我们用递推的想法求每一个n的最大（i，j）对数ans[n]

ans[0] = 0;
    int pre = 0;
    int x = 0;
    for (int i = 1; i <= n; i++)
    {
        for (; i - (1 << x) > 0; x++)
            pre++;
        ans[i] = ans[i - 1] + pre;
  1. 容易发现的另一件事,若某段单调递增，那么这段内没有符合要求的 ( i , j ) 对。

更一般地：若a[i+1]是[1,i+1]的最大前缀值，那么任意 ( j , i + 1 )不符合要求（j<i+1)

  1. 根据3. 我们有了以下的构造想法

若k恰好是某个ans[i],那么前i个数是i，i-1,i-2,.......,2,1,后面的数是i+1,i+2,.......,n-1,n即可

若k夹在ans[i-1]与ans[i]之间，那么后n-i个数是i+1,i+2,.......,n-1,n。前i个数则是在i-1,i-2,......,3,2,1中挑选一个合适的位置插入i即可。

  1. 考虑如何选择插入位置：设t=k-ans[i-1] , top=log2(i).容易证明只需将 i 插入到i-2^(top-t+1)的前面一个数即可。

代码实现

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
int ans[N];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, k;
    cin >> n >> k;
    bool flag = 1;
    ans[0] = 0;
    int pre = 0;
    int x = 0;
    for (int i = 1; i <= n; i++)
    {
        for (; i - (1 << x) > 0; x++)
            pre++;
        ans[i] = ans[i - 1] + pre;
        if (ans[i] == k )
        {
            flag = 0;
            for (int j = i; j >= 1; j--)
                cout << j << " ";
            for (int j = i + 1; j <= n; j++)
                cout << j << " ";
            break;
        }
        else if (ans[i] > k && ans[i - 1] < k)
        {
            flag = 0;
            int t = k - ans[i - 1] - 1;
            int zhishu = log2(i);
            t = zhishu - t;
            t = (1 << t);
            t = i - t ;
            for (int j = i - 1; j >= 1; j--)
            {
                if (j == t )
                    cout << i << " " << j << " ";
                else
                    cout << j << " ";
            }
            for (int j = i + 1; j <= n; j++)
                cout << j << " ";
            break;
        }
    }

    if (flag)
        cout << -1;
    return 0;
}