[POJ1785]Binary Search Heap Construction(笛卡尔树)
2024-08-31 03:33:47
Code
#include <cstdio>
#include <algorithm>
#include <cstring>
#define N 500010
using namespace std; struct info{
int fix,l,r,fa;
char s[10];
friend bool operator <(info a,info b){
return strcmp(a.s,b.s)<0;
}
void clear(){l=r=fa=0;}
}T[N];
char s[233];
int n; inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
} int build(int n){
for(int i=1,j;i<=n;++i){
for(j=i-1;T[j].fix<T[i].fix;j=T[j].fa);
T[i].l=T[j].r;
T[j].r=i;
T[i].fa=j;
}
return T[0].r;
} void dfs(int u){
if(!u) return;
printf("(");
dfs(T[u].l);
printf("%s/%d",T[u].s,T[u].fix);
dfs(T[u].r);
printf(")");
} int main(){
while(~scanf("%d",&n)&&n){
for(int i=0;i<=n;T[i++].clear());
T[0].fix=1e9;
for(int i=1;i<=n;++i){
scanf("%s",s);
sscanf(s,"%[^/]/%d",T[i].s,&T[i].fix);
}
sort(T+1,T+n+1);
int rt=build(n);
dfs(rt);puts("");
}
return 0;
}
最新文章
- Java jdbc 连接oracle
- NGINX 定时器
- OpenWrt网络结构
- HttpWebRequest,HttpWebResponse的用法和用途
- Redis 命令 - Keys
- 1020: [SHOI2008]安全的航线flight - BZOJ
- android系统平台显示驱动开发简要:Samsung LCD接口篇『三』
- Codevs 2776 寻找代表元(二分图匹配)
- [TI DLP Buglist]data type error in illum_EnableIllumination function
- C# Exception类
- 从拉动APP下载谈运营
- [django1.6]跑批任务错误(2006, &#39;MySQL server has gone away&#39;)
- RecyclerView 实现gallery画廊效果
- FBOSS: Building Switch Software at Scale
- 使用PHP中的ajax做登录页面、验证用户名是否可用、动态调用数据库
- MySQL数据库一般设计规则
- Java实现zip压缩文件的解压
- 解决mysql中文乱码问题?
- Mysql 集合链接查询
- hiho一下 第165周#1327 : 分隔相同字符
热门文章
- 收放卷及张力控制 PID调试技巧
- python中的 if __name__ == “__main__”: 有什么用
- 如何清理Windows缩略图缓存?
- Jerry的CRM Middleware(中间件)文章合集
- selenium+python自动化登录脚本
- 【转载】#458 Errors While Converting Between enum and Underlying Type
- C语言 数组的使用
- 云盘+Git GUI实现云盘文件版本号控制
- 2018.9.30 Java中数组的存储与内存分配
- Vue状态管理-Bus