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;
}