首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >1455: 罗马游戏

1455: 罗马游戏

作者头像
HansBug
发布2018-04-11 10:30:10
5660
发布2018-04-11 10:30:10
举报
文章被收录于专栏:HansBug's LabHansBug's Lab

1455: 罗马游戏

Time Limit: 5 Sec  Memory Limit: 64 MB

Submit: 721  Solved: 272

[Submit][Status][Discuss]

Description

罗马皇帝很喜欢玩杀人游戏。 他的军队里面有n个人,每个人都是一个独立的团。最近举行了一次平面几何测试,每个人都得到了一个分数。 皇帝很喜欢平面几何,他对那些得分很低的人嗤之以鼻。他决定玩这样一个游戏。 它可以发两种命令: 1. Merger(i, j)。把i所在的团和j所在的团合并成一个团。如果i, j有一个人是死人,那么就忽略该命令。 2. Kill(i)。把i所在的团里面得分最低的人杀死。如果i这个人已经死了,这条命令就忽略。 皇帝希望他每发布一条kill命令,下面的将军就把被杀的人的分数报上来。(如果这条命令被忽略,那么就报0分)

Input

第一行一个整数n(1<=n<=1000000)。n表示士兵数,m表示总命令数。 第二行n个整数,其中第i个数表示编号为i的士兵的分数。(分数都是[0..10000]之间的整数) 第三行一个整数m(1<=m<=100000) 第3+i行描述第i条命令。命令为如下两种形式: 1. M i j 2. K i

Output

如果命令是Kill,对应的请输出被杀人的分数。(如果这个人不存在,就输出0)

Sample Input

5 100 90 66 99 10 7 M 1 5 K 1 K 1 M 2 3 M 3 4 K 5 K 4

Sample Output

10 100 0 66

HINT

Source

题解:呵呵呵呵呵呵呵呵呵和~~~~这不是左偏树模板题么。。

直接建立一棵左偏树乱搞搞即可。。。(不过我还是头一次写需要维护父亲节点的左偏树,看样子还有点麻烦,不过也还好,就是多几条语句)

 1 /**************************************************************
 2     Problem: 1455
 3     User: HansBug
 4     Language: Pascal
 5     Result: Accepted
 6     Time:4028 ms
 7     Memory:35384 kb
 8 ****************************************************************/
 9  
10 var
11    i,j,k,l,m,n:longint;
12    a,lef,rig,fix,fat,mak:array[0..1500000] of longint;
13    ch:char;
14 function min(x,y:longint):longint;
15          begin
16               if x<y then min:=x else min:=y;
17          end;
18 function max(x,y:longint):longint;
19          begin
20               if x>y then max:=x else max:=y;
21          end;
22 procedure swap(var x,y:longint);
23           var z:longint;
24           begin
25                z:=x;x:=y;y:=z;
26           end;
27 procedure merge(var x,y:longint);
28           begin
29                if x=0 then
30                   begin
31                        fat[y]:=fat[x];fat[x]:=0;
32                        swap(x,y);
33                   end;
34                if y=0 then exit;
35                if a[y]<a[x] then
36                   begin
37                        fat[y]:=fat[x];fat[x]:=0;
38                        swap(x,y);
39                   end;
40                merge(rig[x],y);
41                fat[rig[x]]:=x;
42                fix[x]:=min(fix[lef[x]],fix[rig[x]])+1;
43                if fix[lef[x]]<fix[rig[x]] then swap(lef[x],rig[x]);
44           end;
45 function getfat(x:longint):longint;
46          begin
47               while fat[x]<>0 do x:=fat[x];
48               exit(x);
49          end;
50 begin
51      readln(n);
52      fillchar(lef,sizeof(lef),0);
53      fillchar(rig,sizeof(rig),0);
54      fillchar(fix,sizeof(fix),0);
55      fillchar(fat,sizeof(fat),0);
56      fillchar(mak,sizeof(mak),0);
57      for i:=1 to n do read(a[i]);
58      readln;
59      readln(m);
60      for i:=1 to m do
61          begin
62               read(ch);
63               case upcase(ch) of
64                    'M':begin
65                             readln(j,k);
66                             if (mak[j]=1) or (mak[k]=1) then continue;
67                             j:=getfat(j);k:=getfat(k);
68                             if j=k then continue;
69                             merge(j,k);
70                    end;
71                    'K':begin
72                             readln(j);
73                             if mak[j]=1 then
74                                begin
75                                     writeln(0);
76                                     continue;
77                                end;
78                             j:=getfat(j);
79                             mak[j]:=1;
80                             writeln(a[j]);
81                             merge(lef[j],rig[j]);
82                             j:=lef[j];
83                             fat[j]:=0;
84                    end;
85               end;
86          end;
87      readln;
88 end.    
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2015-04-14 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 1455: 罗马游戏
  • Description
  • Input
  • Output
  • Sample Input
  • Sample Output
  • HINT
  • Source
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档