ACM - 데이터 구조 - 하프 만 트 리 wpl 계산 (최소 힙 + vector)

제목: n 을 드 리 겠 습 니 다. 다음은 n 개의 숫자 를 입력 하 십시오. 해당 문자 의 출현 횟수 (즉, 가중치) 를 표시 합 니 다. 이 가중치 크기 에 따라 하 프 만 트 리 (최소 더미) 를 만 들 고 하 프 만 트 리 의 wpl 을 구 합 니 다.
STL 의 힙 의 응용 1 · 헤드 파일 algorithm 2 · STL 에서 쌓 기와 관련 된 4 개의 함수 1. 쌓 기 Make 만 들 기heap()
make_heap(_First, _Last, _Comp)
         。 int  ,          greater<int>()     。               (>).
vector<int>ptr;
for(int i=0;iint>());

2. 더미 에 데이터 push 추가heap()
push_heap (_First, _Last)
          ,   push_heap ()
ptr.push_back(w1+w2);
push_heap(ptr.begin(),ptr.end(),greater<int>());

3. 더미 에서 데이터 삭제 popheap()
pop_heap(_First, _Last)
    pop_heap()         
int w1=ptr[0];//           
pop_heap(ptr.begin(),ptr.end(),greater<int>());
ptr.pop_back();

4. 더미 정렬 sortheap()
sort_heap(_First, _Last)
             heap 
               ,       ,       。

샘플:
7
1 1 1 3 3 6 6

코드:
#include 
#include   
#include
#include 
#include 
using namespace std;
int n,m,l,k;
const int maxn=260;//zifu
vector<int>ptr;
int calwpl(){ 
    make_heap(ptr.begin(),ptr.end(),greater<int>());
    //for(int i=0;i
    int wpl=0;
    for(int i=1;i//i
        int w1=ptr[0];
        pop_heap(ptr.begin(),ptr.end(),greater<int>());
        ptr.pop_back();
        int w2=ptr[0];
        pop_heap(ptr.begin(),ptr.end(),greater<int>());
        ptr.pop_back();
        printf("w1=%d w2=%d
"
,w1,w2); wpl+=w1+w2; ptr.push_back(w1+w2); push_heap(ptr.begin(),ptr.end(),greater<int>()); } return wpl; } int main(){ ios::sync_with_stdio(false); freopen("1.txt","r",stdin); cin>>n; for(int i=0;icin
>>m; ptr.push_back(m); } int wpl=calwpl(); cout<"wpl="<return 0; }

좋은 웹페이지 즐겨찾기