POJ 1875 Binary Search Heap Construction（treap）

1937 단어 데이터 구조정규 표현 식searchinsert언어.construction
이 문 제 는 기본 적 인 treap 문제 입 니 다. 바로 나 무 를 만 든 다음 에 중간 순 서 를 옮 겨 다 니 며 출력 하면 됩 니 다. 그러나 저 는 treap 이 신마 의 것 이라는 것 을 전혀 몰 랐 습 니 다. 찾 아 보 니 treap 은 이 진 정렬 트 리 와 쌓 인 성질 을 동시에 만족 시 키 는 데이터 구조 이 고 피리 칼 트 리 라 고도 부 릅 니 다.각 노드 는 두 개의 값 이 있 고 하 나 는 키 워드 를 대표 하 며 하 나 는 우선 순 위 를 대표 하 며 주로 왼쪽 회전 과 오른쪽 회전 을 조작 하여 treap 가 그 성질 을 만족 시 킬 수 있 도록 한다.이 문 제 는 처리 하기 편리 하도록 먼저 데 이 터 를 읽 고 키워드 에 따라 정렬 한 다음 에 매번 앞의 노드 를 삽입 한 오른쪽 아들 에 게 삽입 하고 성격 이 만족 하지 않 으 면 우회전 을 하 며 정확 한 위치 에 만 다음 요 소 를 삽입 합 니 다.이 문 제 를 통 해 C 언어의 강력 한 scanf 함수 의 기능 을 알 수 있 습 니 다.% * [] 는 [] 에 있 는 요 소 를 건 너 뛰 고 괄호 에 있 는 요소 가 아 닌 데 이 터 를 만 날 때 까지 읽 지 않 습 니 다.% [^ /] 는 문자열 을 읽 는 것 이 '/' 가 멈 추 었 지만 읽 지 않 습 니 다.
#include <iostream>
#include <cstdio>
#include <string.h>
#include <algorithm>
using namespace std;
struct Node
{
    char str[105];
    int value,ls,rs,pa;
    Node()
    {
        value=pa=ls=rs=0;
        memset(str,0,sizeof(str));
    }
}treap[50005];
bool operator < (const Node a,const Node b)
{
    return strcmp(a.str,b.str)<0;
}
void insert(int i)
{
    int j=i-1;
    while(treap[j].value<treap[i].value)
        j=treap[j].pa;
    treap[i].ls=treap[j].rs;
    treap[j].rs=i;
    treap[i].pa=j;
}
void dfs(int i)   //    
{
    if(i)
    {
        printf("(");
        dfs(treap[i].ls);
        printf("%s/%d",treap[i].str,treap[i].value);
        dfs(treap[i].rs);
        printf(")");
    }
}
int main()
{
    int n;
    while(scanf("%d",&n),n)
    {
        memset(treap,0,sizeof(treap));
        for(int i=1;i<=n;i++)
        {
            scanf("%*[ ]%[^/]/%d",treap[i].str,&treap[i].value);   //   C          ……
        }
        sort(treap+1,treap+n+1);
        treap[0].value=10000000;
        for(int i=1;i<=n;i++)
        {
            insert(i);
        }
        dfs(treap[0].rs);
        printf("
");
    }
}
by zh
codeforces 1000 C [고전 제목] [정렬, 데이터 구조]
큐브 그래픽 코드

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage