程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ3253 Fence Repair 小頂堆+貪心

POJ3253 Fence Repair 小頂堆+貪心

編輯：C++入門知識

給了你N個木棒，求把他們組裝成一根需要的最小花費，每次只能選兩根組裝在一起，需要的花費為兩個木棒之和，

以前遇到過把一整根切開的，那個是DP，這個則有些類似，可是大膽的猜測了一下，直接每次選取所有木棒中最短的兩根，這樣就可以了，那麼貪心是適用的，但是數量很多，而且兩根最短的組裝好了得插回去，這樣不可能每次都排序吧，

這題首先優先隊列肯定是可以做的，

最小堆也是可以的，每次都選出堆裡的最小的兩個求和再放回去即可

隊列本身也就是堆吧，所以差別不大，但是沒用過最小堆最大堆的所以用一次把

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

#define ll long long
#define LL __int64
#define eps 1e-8

//const ll INF=9999999999999;

#define inf 0xfffffff

using namespace std;


//vector > G;
//typedef pair P;
//vector> ::iterator iter;
//
//mapmp;
//map::iterator p;


LL len[20000 + 5];//小頂堆裡的元素，注意len[0]代表小頂堆的元素數目

void clear() {
	memset(len,0,sizeof(len));
}

/****構建小頂堆****/
void heap(int i) {
	int l = i * 2;
	int r = i * 2 + 1;
	int minn = i;
	if(l <= len[0] && len[l] < len[minn])
		minn = l;
	if(r <= len[0] && len[r] < len[minn])
		minn = r;
	if(i != minn) {
		int tmp = len[i];
		len[i] = len[minn];
		len[minn] = tmp;
		heap(minn);
	}
}

/******插入小頂堆*****/
void insertheap(LL x) {
	len[++len[0]] = x;
	LL tmp = len[0];
	while(tmp > 1 && len[tmp] < len[tmp/2]) {
		int t = len[tmp];
		len[tmp] = len[tmp/2];
		len[tmp/2] = t;
		tmp >>= 1;
	}
}

LL get() {
	LL ans1 = len[1];
	len[1] = len[len[0]];//拿走第一個以後，把堆尾的拿到堆首
	len[0]--;
	heap(1);//重新排序
	LL ans2 = len[1];
	len[1] = len[len[0]];
	len[0]--;
	heap(1);
	insertheap(ans1 + ans2);//取出第一小第二小的，然後相加以後再插回小頂堆
	return ans1 + ans2;
}

int main() {
	int n;
	while(scanf("%d",&n) == 1) {
		clear();
		for(int i=1;i<=n;i++) {
			scanf("%I64d",&len[i]);
			insertheap(len[i]);
		}
		LL ans = 0;
		for(int i=1;i