ACM - 데이터 구조 - 하프 만 트 리 wpl 계산 (최소 힙 + vector)
4493 단어 알고리즘 문제 풀이
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;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
vva1025- 알고리즘 입문 경전제목 링크https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3466분석이 dp[T][n]에서 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.