【数据结构】bzoj1455罗马游戏
2024-09-07 15:01:13
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
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
100
0
66
=======================================华丽丽的分割线========================================
发现自己不会写可并堆了肿么办。。。
主要是一个merge操作,每一次选择val比较小的作为根,然后把另外一个合并进来。
每一次通过递归的方式把另一个堆合并在右儿子,然后如果右儿子太大了就和左儿子互换,防止这棵树太不平衡。
然后就做完辣。
时间复杂度O(nlogn),代码如下:
#include <bits/stdc++.h>
#define Maxn 1000007
using namespace std;
int read()
{
int x=,f=;char ch=getchar();
while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}
while (ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
int n,m;
int ls[Maxn],rs[Maxn];
int v[Maxn];
int fa[Maxn],d[Maxn];
bool vis[Maxn];
char ch[];
int find(int x)
{
if (x==fa[x]) return fa[x];
fa[x]=find(fa[x]);
return fa[x];
}
int merge(int x,int y)
{
if (x==) return y;
if (y==) return x;
if (v[x]>v[y]) swap(x,y);
rs[x]=merge(rs[x],y);
if (d[rs[x]]>d[ls[x]]) swap(ls[x],rs[x]);
d[x]=d[rs[x]]+;
return x;
}
int main()
{
n=read();
for (int i=;i<=n;i++)
v[i]=read();
for (int i=;i<=n;i++)
{
fa[i]=i;
d[i]=;
}
memset(vis,true,sizeof(vis));
m=read();
while (m--)
{
scanf("%s",ch);
if (ch[]=='M')
{
int x=read(),y=read();
if ((!vis[x])||(!vis[y])) continue;
int p=find(x),q=find(y);
if (p!=q) fa[p]=fa[q]=merge(p,q);
} else
{
int x=read();
if (!vis[x])
{
printf("%d\n",);
continue;
}
int p=find(x);
vis[p]=false;
printf("%d\n",v[p]);
fa[p]=merge(ls[p],rs[p]);
fa[fa[p]]=fa[p];
}
}
return ;
}
最新文章
- 流行ORM产品优缺点分析--EntityFramework、NHibernate、PetaPoco
- centos6.5下安装qq2012
- 360浏览器兼容模式默认显示ie最高版本
- SQL_递归查询(复杂查询示例)
- AC日记——找最大数序列 openjudge 1.9 10
- [Logstash]使用详解(转)
- 黑盒测试用例设计方法&;理论结合实际 ->; 边界值分析法
- 【转】Java 类的生命周期详解
- 跨时钟域设计【一】——Slow to fast clock domain
- tabbar 嵌套 navigation
- javascript延迟加载及异步(defer和async)
- 如何检测 Android Cursor 泄漏
- 对象序列化 输入输出流概念 InputOutStream OutputStream
- asp.net 程序,当发生找不到文件的错误时,如何正确定位是哪个文件?
- ruby配合gem使用sass
- 浅谈C#语言中的各种数据类型,与数据类型之间的转换
- Android--UI之Radio、Check、Toggle
- jasperreport queryString in
- Java 快速排序法 冒泡排序法 选择排序法 插入排序法
- MySql常用命令集Mysql常用命令2