题解 - Vijos

4

lrj124 LV 10 @ 2016-11-30 12:11:57

评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 1020 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 1020 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 1020 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 1020 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 1020 KiB, score = 10
测试数据 #5: Accepted, time = 46 ms, mem = 1020 KiB, score = 10
测试数据 #6: Accepted, time = 15 ms, mem = 1020 KiB, score = 10
测试数据 #7: Accepted, time = 31 ms, mem = 1024 KiB, score = 10
测试数据 #8: Accepted, time = 31 ms, mem = 1020 KiB, score = 10
测试数据 #9: Accepted, time = 31 ms, mem = 1020 KiB, score = 10
Accepted, time = 154 ms, mem = 1024 KiB, score = 100
代码
#include <algorithm>
#include <cstdio>
using namespace std;
int a[65536],h[65536],i,n;
inline void dfs(int k,int l,int r) {
  h[k] = a[l];
  if (k<<1 > n) return;
  dfs((k<<1)+1,l+1,(l+r+1)>>1);
  dfs(k<<1,((l+r+1)>>1)+1,r);
}
int main() {
  scanf("%d",&n);
  for (int i = 1;i <= n;i++) scanf("%d",&a[i]);
  sort(a+1,a+n+1);
  dfs(1,1,n);
  for (int i = 1;i <= n;i++) printf("%d ",h[i]);
  return 0;
}

1

zztDANTE LV 7 @ 2008-10-20 17:27:54

其实，这题本身不是很难（谁不会建小根堆呢)，但是那个所谓字典序却让人很纠结。于是我们想到：能不能做一个最小字典序的小根堆呢？明显的，我们用快排\堆排得到了这个堆，如：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

但是对于一个最大字典序小根堆来说，，我们应该尽量让左子树大于右子数，于是我们得到的堆是这样的：

1

9 2

13 10 6 3

15 14 12 11 8 7 5 4

也就是说，“左子堆中的任意数大于右子堆中的任意数，且该堆是一个小根堆”该定理适用于最大字典序小根堆中的每一个子堆。

由定义我们就可以写出把一个有序数列变成最大字典序小根堆的procedure(虽然写得很傻，但还是贴出来：

procedure deal(x,y,k:longint);{从deal(1,n)开始}

var

l:longint;

begin

if k>q then exit else{q:=round(ln(n+1)/ln(2))}

inc(r[k]);

b[k,r[k]]:=a[x];

l:=(x+y)div 2;

deal(l+1,y,k+1);

deal(x+1,l,k+1);

end;

{得到的b:

1

9 2

13 10 6 3

15 14 12 11 8 7 5 4

0

最强王者 LV 8 @ 2021-11-26 12:51:40

#include<bits/stdc++.h>//比赛尽量的别用万能头
using namespace std;
int a[65536],h[65536],i,n;
inline void dfs(int k,int l,int r) {
  h[k] = a[l];
  if (k<<1 > n) return;
  dfs((k<<1)+1,l+1,(l+r+1)>>1);
  dfs(k<<1,((l+r+1)>>1)+1,r);
}
int main() {
  scanf("%d",&n);
  for (int i = 1;i <= n;i++) scanf("%d",&a[i]);
  sort(a+1,a+n+1);
  dfs(1,1,n);
  for (int i = 1;i <= n;i++) printf("%d ",h[i]);
  return 0;
}

0

ibelieve LV 7 @ 2013-03-24 11:46:23

var a,h:array[0..65536] of longint;
i,n :longint;
procedure sort(l,r :longint);
var i,j,m:longint;
begin
i:=l; j:=r; m:=a[(l+r)>>1];
repeat
while a[i]<m do inc(i);
while a[j]>m do dec(j);
if i<=j then begin
a[0]:=a[i]; a[i]:=a[j]; a[j]:=a[0];
inc(i); dec(j);
end;
until i>j;
if l<j then sort(l,j);
if i<r then sort(i,r);
end;
procedure put(k,l,r:longint);
begin
h[k]:=a[l];
if k<<1>n then exit;
put(k<<1+1,l+1,(l+r+1)>>1);
put(k<<1,(l+r+1)>>1+1,r);
end;
begin
readln(n);
for i:=1 to n do read(a[i]);
sort(1,n); put(1,1,n);
for i:=1 to n do write(h[i],' ');
end.

上海红茶馆 via libjudge
编译成功

测试数据 #0: Accepted, time = 15 ms, mem = 1144 KiB, score = 10
测试数据 #1: Accepted, time = 15 ms, mem = 1144 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 1144 KiB, score = 10
测试数据 #3: Accepted, time = 30 ms, mem = 1144 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 1144 KiB, score = 10
测试数据 #5: Accepted, time = 152 ms, mem = 1144 KiB, score = 10
测试数据 #6: Accepted, time = 212 ms, mem = 1144 KiB, score = 10
测试数据 #7: Accepted, time = 208 ms, mem = 1144 KiB, score = 10
测试数据 #8: Accepted, time = 210 ms, mem = 1144 KiB, score = 10
测试数据 #9: Accepted, time = 210 ms, mem = 1144 KiB, score = 10
Summary: Accepted, time = 1067 ms, mem = 1144 KiB, score = 100

0

chengrui LV 10 @ 2009-11-08 07:27:58

强烈鄙视VJ评测机.......

虽然你们难，我也知道，

但是这太让人无语.....

n

0

木子日匀 LV 10 @ 2009-08-29 14:35:34

先快排再分治。。

procedure done(top,l,r:longint);

begin

a[top]:=n[l];

inc(l);

if 2 * top < k then

begin

done(2*top,(l+r) div 2+1,r);

done(2*top+1,l,(l+r) div 2);

end;

end;

0

linad2d LV 8 @ 2009-08-20 16:13:10

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：运行超时|无输出...

├ 测试数据 07：运行超时...

├ 测试数据 08：运行超时...

├ 测试数据 09：运行超时...

├ 测试数据 10：运行超时...

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：50 有效耗时：0ms

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

交了无数次才发现没审好题……

未换行成千古恨……

0

hzx2008 LV 10 @ 2009-08-05 18:24:28

如此水题：简单秒杀

编译通过...├ 测试数据 01：答案正确... 0ms├ 测试数据 02：答案正确... 0ms├ 测试数据 03：答案正确... 0ms├ 测试数据 04：答案正确... 0ms├ 测试数据 05：答案正确... 0ms├ 测试数据 06：答案正确... 0ms├ 测试数据 07：答案正确... 0ms├ 测试数据 08：答案正确... 0ms├ 测试数据 09：答案正确... 0ms├ 测试数据 10：答案正确... 0ms-------------------------Accepted 有效得分：100 有效耗时：0ms

附核心程序：鼠标拖动即可

procedure work(k:longint);begin if k>n then exit; inc(j); w[k]:=a[j]; work(2*k+1); work(2*k);end;

0

luyifan LV 10 @ 2009-05-03 14:20:36

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

qsort+后序构造 ((具体实现类似于线段树的那种递归))

0

唐钰小宝 LV 10 @ 2009-04-04 22:09:26

qsort+后序构造（贪心）

0

332404521 LV 9 @ 2009-03-15 21:00:43

当我思考怎样快速找到某结点左子结点的个数时得走头无路想用暴力判断法时，发现原题一句话：为了简化题目，数据保证n=2^k-1，即保证最后的堆是一棵满二叉树。

0

xiaoX LV 10 @ 2008-12-16 21:22:20

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

通过　　400人

提交　　1403次

本来应该是 400、1400 的…… 由于急着提交…… 结果连挂3次…… 第四次才过…… 5555555555555…………

0

greenmoon55 LV 4 @ 2008-11-13 22:20:38

Dolphin 第8组超时，其他都0ms。Puppy就全0msAC了。

0

我是天才他哥 LV 10 @ 2008-11-13 19:13:57

0MS

此题是我的第200题！

celebrate!

0

wmp LV 3 @ 2008-11-12 13:06:13

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

0

LIUHY LV 3 @ 2008-11-10 10:36:28

vivid puppy 好

0

karatew LV 3 @ 2008-11-08 10:07:11

我恨Dolphin……

桶排序，10^5的算法超时了……

0

Big-P LV 3 @ 2008-11-02 16:33:45

PROGRAM P1469_Orz;

VAR

a,b:array[0..200000] of longint;

n,i,j:longint;

PROCEDURE egg(k:longint);

begin

b[k]:=a[j];

inc(j);

if 2*k>n then exit;

egg(2*k+1);

egg(2*k);

end;

BEGIN

readln(n);

for i:=1 to n do

read(a[i]);

j:=1;

qqsort(1,n);

egg(1);

for i:=1 to n-1 do

write(b[i],' ');

writeln(b[n]);

END.

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：运行超时...

├ 测试数据 08：运行超时...

├ 测试数据 09：运行超时...

├ 测试数据 10：运行超时...

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：60 有效耗时：0ms

为什么...请教大牛了...

0

boyzkk LV 10 @ 2008-11-01 20:42:07

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

爽！！！

0

吴豪 LV 8 @ 2008-10-29 18:59:47

首先通过任意方法排好序（不降）

a1 (a2 a3 .... ak) (ak+1 .... an)

< < < ....

然后每次按这样的方式划分，把第一个作为根节点，两个括号作为右左子树。

这样建起一颗树（具体实现类似于线段树的那种递归）。

最后按层顺次输出即可。

题解

61 条题解

偷懒的小X

信息

状态

开发

支持

题解

61 条题解

偷懒的小X

信息

状态

开发

支持

还没有账户？

登录