BZOJ 1078 사선

1078: [SCOI 2008] 사선 더미
Time Limit: 10 Sec Memory Limit: 162 MB Description
경사 더미 (skew heap) 는 자주 사용 하 는 데이터 구조 이다.그것 도 이 진 트 리 이 고 이 진 트 리 와 같은 쌓 인 성질 을 만족 시 킵 니 다. 모든 비 근 결점 의 값 은 아버지 보다 큽 니 다.그래서 전체 경사 더미 에서 뿌리의 값 이 가장 작다.그러나 경사 더 미 는 균형 이 잡 힐 필요 가 없 으 며, 각 결점 의 좌우 아들 의 크기 관계 도 규정 되 어 있 지 않다.이 문제 에 서 는 경사 더미 에 있 는 각 요소 의 값 이 모두 다르다.경사 로 H 에 새로운 요소 X 를 삽입 하 는 과정 은 재 귀적 으로 진행 된다. H 가 비어 있 거나 X 가 H 보다 작은 뿌리 결점 일 때 X 는 새로운 뿌리 로 변 하고 원래 의 뿌리 (있 으 면) 는 X 의 왼쪽 아들 로 변 한다.X 가 H 보다 큰 뿌리 결산 점 일 때 H 뿌리 결산 점 의 두 개의 서브 트 리 는 교환 되 고 X (재 귀) 는 교환 후의 왼쪽 서브 트 리 에 삽 입 됩 니 다.0 ~ n 의 결점 을 각각 한 번 씩 포함 하 는 경사 더 미 를 드 립 니 다.이 경사 더 미 는 빈 트 리 에 순서대로 이 결점 을 삽입 하여 얻 을 수 있 도록 결점 서열 을 구하 십시오.만약 답 이 유일한 것 이 아니라면, 출력 사전 의 순서 가 가장 작은 해 입 니 다.입력 은 틀림없이 풀 릴 것 이다.
Input
첫 줄 에는 정수 n 이 포함 되 어 있 습 니 다.두 번 째 줄 은 n 개의 정수 d1, d2,..., dn, di < 100 은 i 가 di 의 왼쪽 아들, di > = 100 은 i 가 di - 100 의 오른쪽 아들 임 을 나타 낸다.분명히 0 은 항상 루트 이기 때문에 입력 에 d0 이 포함 되 어 있 지 않 습 니 다.
Output
한 줄 에 만 n + 1 정수, 즉 사전 순서 가 가장 작은 삽입 순 서 를 포함 합 니 다.
Sample Input
6
100 0 101 102 1 2
Sample Output
0 1 2 3 4 5 6
사고: 시 뮬 레이 션 문제, 물 건 너.< Xs 소스 ~ > 에서 따 온 것 은 경사 로 에 삽 입 된 마지막 노드 에 대해 두 가지 성질 을 내 놓 을 수 있 습 니 다. (1) 이것 은 나무 중의 극좌 노드 (2) 일 것 입 니 다. 오른쪽 나무 가 없 을 것 입 니 다. 그리고 모든 경사 로 에 있 는 점 을 발견 할 수 있 습 니 다. 만약 에 그 가 왼쪽 나무 가 없 으 면 오른쪽 나무 도 없 을 것 입 니 다.(잎 이 아니면 반드시 왼쪽 나무 가 있다 는 거 야. 쓸데없는 소리 하지 마...) 그리고 마 토 발 라 발 라 가 한 무더기 말 했다...(알 아 볼 수 없다...) 최종 결론 을 얻 었 다. 마지막 에 삽 입 된 노드 X 는 반드시 만족 (1) (2) 이 고 깊이 가 가장 작다. 그의 왼쪽 나무 가 한 노드 만 있 는 것 을 제외 하고.(삽입 대기 열의 최소 화 를 만족 시 키 기 위해) 그래서 방법 은 다음 과 같다. (1) 위의 결론 에 따라 현재 삽 입 된 노드 를 찾 아서 (2) 이 점 을 삭제 하고 (3) 조상 들 의 좌우 자 수 를 모두 교환 했다.

#include
#include 
#include 
#include 
#include 
#include 
using namespace std;

int n,rt,x,a[105][2],fa[105],ans[105];

void work(){
    int p, f, son, fl, cnt = n + 1;
    while( cnt ){
        fl = 0, p = rt;
        while(a[p][1] != -1) p = a[p][0];//                  
        son = a[p][0];
        if(son != -1 && a[son][0] == -1 && a[son][1] == -1) p = son;
        ans[cnt--] = p;//   
        f = fa[p], son = a[p][0];
        if(p == rt) rt = son, fl = 1, fa[son] = -1;
        else if (son != -1) a[f][0] = son, fa[son] = f;
        else a[f][0] = -1;
        while(p != rt && !fl){//      
            p = fa[p];
            swap(a[p][0], a[p][1]);
        }
    }
}

int main(){
    scanf("%d",&n);
    memset(a, -1, sizeof(a));
    memset(fa, -1, sizeof(fa));
    for(int i=1; i<=n; i++){
        scanf("%d", &x);
        if(x >= 100) a[x-100][1] = i, fa[i] = x-100;
        else a[x][0] = i, fa[i] = x;
    }
    rt = 0;
    work();
    for(int i=1; i<=n+1; i++) printf("%d ", ans[i]);
}