#简单分治#[jzoj 2940] 偷懒的小X

news/2024/2/21 1:37:17

题目

话说3008年的Orz教主节,全民狂欢,传递教主圣火,以致万人空巷,股票飞涨。真乃锣鼓喧天,鞭炮齐鸣,红旗招展,人山人海呐。可是小X为了准备NOIP3008,不得不待在家里好好Coding。小X希望早点结束当天的任务,加入圣火传递队伍中去。
在这个不亚于狂欢节的日子里,小X的老师却“公然违抗”休假法令,布置小X写一个小根堆,但是小X不会堆的操作,所以想了一个偷懒的办法:
  堆是一棵完全二叉树,每个结点有一个权。小根堆的根的权最小,且根的两个子树也是一个堆。可以用一个数组a来记录一棵完全二叉树,a[1]为根结点,若结点a[j]不是根结点,那么它的父亲为a[j/2](取下整);若结点a[k]不是叶子结点,那么它的左儿子为a[2k],它的右儿子为a[2k+1]。
  他希望一组数据按一定顺序依次插入数组中(即第i个数为a[i]),最后得出来就已经是一个堆,即不需要任何交换操作,若有多种方法,输出字典序最大的一组,显得这个数据更乱。


解题思路

对于当前序列,我们肯定是选最小的放在堆顶。
然后分左右子树(大的分左边,小的分右边),显然可以重复现在的选择。


代码

#include<cstdio>
#include<algorithm>
using namespace std;
int n,a[70000],m,b[70000];
void fz(int l,int r,int k){b[k]=a[l]; if (l==r) return; int mid=(l+r)>>1; fz(mid+1,r,2*k); fz(l+1,mid,2*k+1); 
}
int main(){scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); sort(a+1,a+n+1); fz(1,n,1); for(int i=1;i<n;i++) printf("%d ",b[i]); printf("%d\n",b[n]); 
}

http://www.ppmy.cn/news/304083.html

相关文章

poj2940(贪心)

Wine Trading in Gergovia Time Limit: 1000MS Memory Limit: 65536KTotal Submissions: 2894 Accepted: 1320 Description As you may know from the comic “Asterix and the Chieftain’s Shield”, Gergovia consists of one street, and every inhabitant of the city is …

2940: 结构体变量的使用。

时间限制: 1 Sec 内存限制: 128 MB 提交: 526 解决: 359 [ 提交][ 状态][ 讨论版] 题目描述 定义一个结构体变量&#xff0c;输入数据&#xff0c;输出变量内容。主函数在程序的最后并且已给出&#xff0c;提交程序的其他部分即可。 int main() { student student1; cin>…

POJ 2940 求和

时间限制: 1000ms 内存限制: 65536kB 描述 求Sn a aa aaa … aa…a 的值&#xff08;最后一个数中 a 的个数为 n &#xff09;&#xff0c;其中 a 是一个1~9的数字&#xff0c;例如&#xff1a; 2 22 222 2222 22222 &#xff08;此时 a2 n5 &#xff09; 输入 一行&…

递归与非递归:实现求第n个斐波那契数。实现n^k。输入一个非负整数,返回组成它的数字之和。将参数字符串中的字符反向排列。实现strlen。求n的阶乘。打印一个整数的每一位。

1.递归和非递归分别实现求第n个斐波那契数。 #define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<stdlib.h>int fib(int n) {if (n < 2)return 1;elsereturn fib(n - 1) fib(n - 2); }int main() {int n 0;int ret 0;scanf("%d", &…

高精度 hdu 2940 Hex Factorial

直接暴力打表&#xff0c;也可以在代码外打表复制粘贴 #include<cstdio> #include<cstring> #include<cmath> using namespace std; const int BIT 16; struct BIGint{int bit[200];void MEMset(){memset(bit,0,sizeof(bit));bit[1] 1;}void multiply(int …

POJ 2940 Wine Trading in Gergovia [贪心]

Description As you may know from the comic “Asterix and the Chieftain’s Shield”, Gergovia consists of one street, and every inhabitant of the city is a wine salesman. You wonder how this economy works? Simple enough: everyone buys wine from other inha…

HDU 2940 Hex Factorial

题目求N&#xff01;中有多少个0 用16进制高精度模拟 想起来一起以前做过的一道题&#xff0c;求末尾有多少个0&#xff0c;不能取0前边的3 4个非零位存下来进行计算&#xff0c;误差太大 #include <iostream> #include <fstream> #include <cstring> usin…

poj 2940 求和

#include <stdio.h>#include <stdlib.h>int main(){ int i,n,a,sum; sum0; scanf("%d%d",&a,&n); for(i0;i<n;i) { suma; aa%1010*a; } printf("%d\n",sum); return 0;} 转载于:https://www…

稳定的LDO芯片推荐

推荐几款稳定性较好的LDO芯片&#xff1a; LM2937&#xff1a;这是一款常用的低噪声LDO&#xff0c;具有良好的稳定性和高效率。 LM2675&#xff1a;这是一款高效率的LDO&#xff0c;特别适用于需要高输出精度的应用。 LM2937-N&#xff1a;这是LM2937的低噪声版本&#xff0c;…

poj2940

简单题 View Code #include <iostream>#include <cstdlib>#include <cstring>#include <cstdio>using namespace std;#define maxn 100005int n, f[maxn];void input(){for (int i 0; i < n; i) scanf("%d", &f[i]);}void w…

百练 2940 求和

题目链接&#xff1a;http://bailian.openjudge.cn/practice/2940 # include <stdio.h>int main() {int Sn,a,a_back,n;int i;scanf("%d%d",&a,&n);a_backa; Sna;for(i1;i<n;i){aa*10a_back;SnSna;}printf("%d\n",Sn); return 0; } &am…

HDOJ2940高精度阶乘优化版

题目链接&#xff1a;hdoj2940-Hex Factorial 在此转到关于本书博客ACM大学生程序设计竞赛在线题库最新精选题解&#xff08;赵端阳&#xff09;部分解析 原书和网上大多数程序都是从0到200最高位不断加乘&#xff0c;然后判断前导零位置。实际上阶乘是递增记录的&#xff0c;可…

jzoj2940. 生成输入数据

Description 首先看到题目别太开心&#xff0c;这题可不是让你出数据&#xff5e;^_* 背景神马的就忽略了。这题就是给你一棵带边权的树&#xff0c;然后这棵树是某个完全图唯一的最小生成树。问原来的完全图中所有边可能的最小边权和是多少。 完全图是任意两个点之间都有边相连…

2940. 凤凰古城

单点时限: 2.0 sec 内存限制: 256 MB 凤凰古城&#xff0c;位于沱江之畔&#xff0c;群山环抱&#xff0c;关隘雄奇。碧绿的沱江依着城墙缓缓流淌&#xff0c;叠翠的南华山麓倒映江中。江中渔舟游船数点&#xff0c;山间暮鼓晨钟兼鸣&#xff0c;悬崖上的吊脚楼轻烟袅袅&…

hdu 2940

简单的大数乘法&#xff0c;直接改16进制~~ #include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> #include <algorithm> #define maxn 3010 #define INF 0x7fffffff #define ull unsigned long long using namespace std…

POJ - 2940

题目 As you may know from the comic “Asterix and the Chieftain’s Shield”, Gergovia consists of one street, and every inhabitant of the city is a wine salesman. You wonder how this economy works? Simple enough: everyone buys wine from other inhabitants …

poj 2940

Wine Trading in Gergovia Time Limit: 1000MS Memory Limit: 65536KTotal Submissions: 3187 Accepted: 1454 Description As you may know from the comic “Asterix and the Chieftain’s Shield”, Gergovia consists of one street, and every inhabitant of the city is …

BZOJ2940 条纹

条纹游戏是一个双人的游戏。所需要的物品有一个棋盘以及三种颜色的长方形条纹&#xff0c;这三种颜色分别是红色、绿色和蓝色。所有的红色条纹的尺寸是c*1&#xff0c;所有的绿色条纹的尺寸是z*1&#xff0c;所有的蓝色条纹的尺寸是n*1&#xff0c;这里c,z,n是正整数。每种颜色…

Linux Crash/Hang on Bay Trail/J1900/N2940

近几年的linux kernel, 尤其是4.1以后,在Bay Trail平台上会随机挂起和死机,亲测j1900,死机非常频繁,而且死机前毫无征兆,直接就挂起了,console也没有相应。 这个问题在bugzilla.kernel.org上已经吵翻了,从2015年年初,一直到现在,仍然没有彻底解决,临时方案有几个,但…

docker下载慢,卡顿解决办法——免费安装人人都有的docker加速器

点我获取阿里云免费镜像加速器 先确认一下docker版本>1.10.0 docker -v 人人都有免费哦~ 进入对应目录查看&#xff0c;我是root用户且没有 daemon.json文件 那就创建一个 vim daemon.json内容就是网页复制的那个 最后重启 systemctl daemon-reloadsystemctl restart do…
最新文章