首页 > 其他分享 >牛牛的构造(构造)

牛牛的构造(构造)

时间:2023-01-07 18:44:07浏览次数:71  
标签:二元 牛牛 递增 构造 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

相关文章

  • 牛牛取石子(对称策略/模拟棋)
    题目链接题目描述:牛牛和牛妹在玩游戏,他们的游戏规则是这样的:一共有两堆石子,第一堆有\(a\)个,第二堆有\(b\)个,牛牛和牛妹轮流取石子,牛牛先手,每次取石子的时候只能从以......
  • 牛牛的构造
    牛牛的构造链接:https://ac.nowcoder.com/acm/contest/49888/E来源:牛客网题意:构造一个长度为n的排列,使得这个排列恰好存在k个二元组[i,j],满足1≤i<j≤n&......
  • 洁净工程洁净室的气密构造
    洁净工程洁净室的气密构造。洁净工程洁净室与相邻房间之间包括不同洁净度等级的洁净室之间,洁净室与非洁净室之间以及洁净室与室外环境之间,根据洁净室特性均应保持规定的......
  • 模型驱动设计的构造块(下)——DDD
    3.领域对象的生命周期每个对象都有生命周期,如下图所示。对象自创建后,可能会经历各种不同的状态,直至最终消亡——要么存档,要么删除。当然很多对象是简单的临时对象,仅......
  • c#的构造函数及构造函数的调用
    C#构造函数的特性一、什么是C#构造函数?Construct,Function   C#构造函数是一种特殊的成员函数,它主要用于为对象分配存储空间,对数据成员进行初始化.   C#构造......
  • canvas德卡斯特里奥算法构造贝塞尔曲线可视化实现
    前言在现代js教程中看到通过德卡斯特里奥算法构造贝塞尔曲线的demo,觉得很有意思,尝试自己写一下目标效果如下吐槽一下,我看到文章底部才发现原来这里的demo是svg做的开......
  • CC6 牛牛的排序
    描述牛牛试图给一个长度为n整数数组排序,即实现一个voidsort(int*array,intn)输入描述:第一行输入一个正整数n,表示数组长度。第二行输入n个正整数,表示数组中每......
  • 析构函数 和 构造函数 和 base使用
    classA//基类First{~A()//析构函数{Console.WriteLine("~A()析构函数");}publicA(){......
  • C++11:移动构造函数
    1.拷贝构造函数中的深拷贝问题在C++98/03标准中,如果想用其它对象初始化一个同类的新对象,只能借助类中的拷贝构造函数。拷贝构造函数的实现原理很简单,就是为新对象复制......
  • C++:拷贝构造函数
    1.拷贝和拷贝构造函数拷贝和复制是一个意思,对应的英文单词都是copy。对于计算机来说,拷贝是指用一份原有的、已经存在的数据创建出一份新的数据,最终的结果是多了一份相同......