首页 > 代码库 > yzoi2223集合构造的详细解法
yzoi2223集合构造的详细解法
Description - 问题描述
集合M的定义如下:
- 1是M中的元素
- 如果x是M中的元素,那么2x+1和4x+5都是M中的元素
那么,集合M中,最小的n个数是哪些?
Input - 输入数据
一个整数n(1<=n<=100 000)
Output - 输出数据
n个从小到大的整数,空格分隔。
仔细一分析便可推知最后需要输出的数一定是单调递增的。在当时做这题的时候,旁边的gxy同学直接从1开始暴力枚举所有的奇数(2x+1和4x+5肯定是一个奇数),然后判断和前面的数是否构成2x+1或4x+5的关系,是的话就输出,否则便continue,这样的话算法复杂度就达到了O(n^2),最后还是有一个点无法通过。那么,是否还有更好的方法呢?
事实上,由前面的单调递增可以知道:假如我们用一个数组来保存输出的数,那么这个数组肯定是2x+1产生的数再并上4x+5产生的数。这样一来也就明了了只要我们定义一个a队列来保存2x+1产生的数,用一个b队列保存4x+5产生的数。每次将a的对头与b的对头进行比较,则会出现3种情况:(A)a对头>b对头 (B)a对头=b对头 (C)a对头<b对头 这时只需要将较小者送人x来执行下一次的2x+1和4x+5,同时也不要忘记将x输出。在经过多方的查证后,我才得以知道这是使用了单调队列的思想,下面给出百度里给它的定义以有助于大家的理解:单调队列,即单调的队列。使用频率不高,但在有些程序中会有非同寻常的作用。(大概就是诸如这类的题目吧)
举例
不妨用一个问题来说明单调队列的作用和操作:
不断地向缓存数组里读入元素,也不时地去掉最老的元素,不定期的询问当前缓存数组里的最小的元素。
最直接的方法:普通队列实现缓存数组。
进队出队都是O(1),一次查询需要遍历当前队列的所有元素,故O(n)。
好了,接下来给出代码,仅供参考:
1 #include<iostream> 2 using namespace std; 3 const int maxn=1000000+10; 4 int a[maxn],b[maxn]; 5 int x=1,n,total=1; 6 int front1=1,front2=1,tail1=0,tail2=0; 7 int main() 8 { 9 cin>>n;10 while(total<=n)11 {12 if(total==n)13 cout<<x;14 else15 cout<<x<<‘ ‘;16 17 tail1++;18 a[tail1]=2*x+1;19 20 tail2++;21 b[tail2]=4*x+5;22 23 if(a[front1]>b[front2])24 {25 x=b[front2];26 front2++;27 28 }29 else30 {31 if(a[front2]<b[front2])32 {33 x=a[front1];34 front1++;35 }36 else37 {38 x=a[front1];39 front1++;40 front2++;41 }42 }43 total++;44 }45 return 0;46 }
最后,欢迎大家的指教。
yzoi2223集合构造的详细解法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。