아 날로 그 poj 2166 Heapsort

제목 링크:
http://poj.org/problem?id=2166
제목 의 대의:
쌓 아 올 리 고 정렬 하 는 과정 을 거 쳐 교환 하 는 횟수 가 가장 많 습 니 다.
문제 풀이 방향:
이 문 제 는 어젯밤 에 생각 을 좀 했 는데 생각 이 안 나 서 오늘 아침 에 같이 오 자마자 생각 이 났 다.
분석:쌓 기 정렬 을 가장 많이 교환 하려 면 이렇게 구 조 를 구성 할 수 있 습 니 다.매번 1 을 마지막 으로 교환 할 수 있 습 니 다.재 분석 을 통 해 알 수 있 듯 이 전달 을 통 해 현재 의 나무 구 조 를 얻 을 수 있다.
지금 모두 n 개의 노드 가 있다 고 가정 하면 save[1]=n,save[n]=1 이 있 습 니 다.쌓 인 지붕 을 제거 한 후에 1 은 쌓 인 지붕 으로 옮 겼 습 니 다.1 을 n-1 번 위치 로 옮 기 려 면 노드 가 n-1 일 때 나무의 구 조 를 빌려 n-1 의 경우 에 만 사용 할 수 있 습 니 다.쌓 인 지붕 에서 마지막 요소 까지 의 경 로 를 따라 오른쪽 회전 한 위치(아들 은 아버지 와 같 고 순서대로 쌓 인 지붕 으로 업데이트 할 수 있 습 니 다)를 통일 시 킬 수 있 습 니 다.그리고 n 을 쌓 아 올 리 고 1 은 n 번 위치 에 놓 습 니 다.이렇게 이해 하면 예전 에 구조 트 리 구 조 를 뒤로 넘 기 면 답 이 나온다.
코드:

//#include<CSpreadSheet.h>

#include<iostream>
#include<cmath>
#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<string>
#include<string.h>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<ctime>
#include<bitset>
#define eps 1e-6
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define ll __int64
#define LL long long
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
#define M 1000000007
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;

#define Maxn 550000

int save[Maxn];

int main()
{
   //freopen("in.txt","r",stdin);
   //freopen("out.txt","w",stdout);
   int n;

   while(~scanf("%d",&n))
   {
       save[1]=1;

       for(int i=2;i<=n;i++)
       {
           int cur=i-1;
           while(cur>=1) // n-1      n   
           {
               save[cur]=save[cur/2]; //            
               cur/=2; //        
           }
           save[1]=i; //             
           save[i]=1; //        1
       }
       printf("%d",save[1]);
       for(int i=2;i<=n;i++)
            printf(" %d",save[i]);
       putchar('
');
   }
   return 0;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

아 날로 그 예약 프로그램 (운전면허 시험)

최근 한 달 넘 게 주말 내 내 차 를 연습 하 느 라 바쁘다.전에 시 뮬 레이 터 를 한 번 예 약 했 는데 갑자기 일이 생 겨 서 못 갔 어 요.다시 예약 하려 면 3 주 후에 줄 을 서 야 합 니 다.그래서 어...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

아 날로 그 poj 2166 Heapsort

좋은 웹페이지 즐겨찾기