牛牛的构造（构造）

标签：二元 牛牛 递增 构造 int 数组 区间 inc

题目链接

题目描述：

请你给出一个长度为 \(n\) 的数组 \(a\) ，数组 \(a\) 中的数是 \(1\) 到 \(n\) 的排列，即其中每个数的范围都是 \([1,n]\) ，且每个数各不相同。同时使得这个数组恰好存在 \(k\) 个二元组 \((i,j)\) ，满足 \(1≤i<j≤n\) , \(a_i−a_j=2^x (x∈N)\)。如果不存在一个数组满足条件，输出 \(-1\)，如果存在多个数组都满足条件，输出任意一个数组即可。\((x∈N)\)指 \(x\) 表示某个非负整数。

输入描述：

第一行输入两个整数 \(n,k\) 。\((1≤n≤10^6,0≤k≤10^9 )\) 。

输出描述：

输出一行，一个长度为 \(n\) 满足条件的数组，两个数之间以一个空格分隔。

样例1：

input:

3 1

output:

1 3 2

说明：

\(1\) \(3\) \(2\) 这个数组仅存在一个二元组 \((2,3)\) 满足条件。

\(a_2 - a_3 = 2^0\)

样例2：

input:

1 100

output:

-1

AC代码：

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;

int k, n;
int a[N];
// b[i]表示i最多能形成多少个二元组
// 即i, i - 1, i - 2,..., 1这样的排列中i能形成多少个二元组
int b[N]; 

int main()
{
    scanf("%d%d", &n, &k);

    int num = 0;

    // 对数组b进行构造
    for(int i = 1; i <= n; i *= 2)
    	b[i + 1] = 1;

    for(int i = 1; i <= n; i ++)
    	b[i] = b[i - 1] + b[i];

    // 对n, n - 1, n - 2,..., 1这样的数组能形成的二元组的数量和相加
    // num为这个1到n的排列能形成的最多的二元组的数量
    for(int i = 1; i <= n; i ++)
    	num += b[i];

    // num < k代表这个排列不能形成k个二元组
    if(num < k)
    {
    	printf("-1");
    	return 0;
    }

    // 如果num >= k则可以
    // 得到的数组的形式为一个递减区间和一个递增区间
    // 则这个数组的能形成的二元组的数量为：
    // 递减区间的数能形成的二元组的数量的和
    // 递增区间不会形成二元组
    // 如：7 6 5 1 2 3 4的二元组的数量为b[7] + b[6] + b[5]
    vector<int> dec, inc;

    // 从后往前枚举
    for(int i = n; i >= 1; i --)
    {
    	// 只要k >= b[i]就把i放入递减区间
    	if(k >= b[i])
    	{
    		k -= b[i];

    		dec.push_back(i);
    	}
    	// 否则就放入递增区间
    	else
    	{
    		inc.push_back(i);
    	}
    }

    // 因为是从后往前枚举，最后要将递增区间翻转
    reverse(inc.begin(), inc.end());

    // 输出递增递减区间
    for(auto j : dec)
    	printf("%d ", j);
    for(auto j : inc)
    	printf("%d ", j);

    return 0;
}

标签：二元,牛牛,递增,构造,int,数组,区间,inc
From： https://www.cnblogs.com/KSzsh/p/17033198.html