POJ 3253 울타리 수리 (호 프 만 인 코딩 + 최소 더미)
#include <stdio.h>
#define MAX_PLANKS 20000
int numOfPlanks;
long long length[MAX_PLANKS + 1];
int heapSize;
void swap(long long *a, long long *b){
long long c = *a;
*a = *b;
*b = c;
}
int getParent(int child){
return child >> 1;
}
int leftChild(int parent){
return parent << 1;
}
int rightChild(int parent){
return (parent << 1) + 1;
}
void minHeapify(int parent){
int smallest = parent;
int left = leftChild(parent);
if (left <= heapSize && length[left] < length[smallest])
smallest = left;
int right = rightChild(parent);
if (right <= heapSize && length[right] < length[smallest])
smallest = right;
if (smallest != parent){
swap(&length[smallest], &length[parent]);
minHeapify(smallest);
}
}
void buildMinHeap(){
int parent;
for (parent = heapSize >> 1; parent >= 1; parent--)
minHeapify(parent);
}
long long extractMin(){
long long min = length[1];
length[1] = length[heapSize];
heapSize--;
minHeapify(1);
return min;
}
void insert(long long len){
heapSize++;
length[heapSize] = len;
int index = heapSize;
int parent;
while (( parent = getParent(index) ) >= 1 && length[parent] > length[index]){
swap(&length[index], &length[parent]);
index = parent;
}
}
int main(){
scanf("%d", &numOfPlanks);
int i;
for (i = 1; i <= numOfPlanks; i++)
scanf("%d", &length[i]);
heapSize = numOfPlanks;
buildMinHeap();
long long one, another;
long long minCost = 0;
while (heapSize > 1){
one = extractMin();
another = extractMin();
minCost += one + another;
insert(one + another);
}
// long long %lld
printf("%lld
", minCost);
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
POJ3071: Football(확률 DP)Consider a single-elimination football tournament involving 2n teams, denoted 1, 2, …, 2n. After n rounds, only one team...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.