POJ 3253 Fence Repair

哈夫曼思想，优先队列解决

手打版

就把上一篇堆的代码做了点改动

/*
poj  3253
368K	47MS
*/

#include<map>
#include<set>
#include<list>
#include<queue>
#include<stack>
#include<ctime>
#include<cmath>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>

#define MAXN 30005
#define MAX_INT 2147483647
#define FA(x) (x>>1) 
#define LC(x) ((x<<1))
#define RC(x) ((x<<1)|1)
#define MID(x,y) ( (x + y) >> 1 )
#define TIME_BEGIN double t1 = clock()
#define TIME_END double t2 = clock();printf("\n%.2lfms\n",t2-t1)

using namespace std;

int size,top = 1;
__int64 heap[MAXN];

bool cmp(__int64 a,__int64 b)
{
	return a < b;
}

void up(int id)
{
	if(id == 1)
		return ;
	if(!cmp(heap[FA(id)] , heap[id]))
	{
		swap(heap[FA(id)] , heap[id]);
		up(FA(id));
	}
}

void down(int id)
{
	if(RC(id) <= size)
	{
		if(cmp(heap[LC(id)] , heap[RC(id)]) && cmp(heap[LC(id)] , heap[id]))
		{
			swap(heap[LC(id)] , heap[id]);
			down(LC(id));
		}
		else if(!cmp(heap[LC(id)] , heap[RC(id)]) && cmp(heap[RC(id)] , heap[id]))
		{
			swap(heap[RC(id)] , heap[id]);
			down(RC(id));
		}
	}
	else if(LC(id) <= size)
	{
		if(cmp(heap[LC(id)] , heap[id]))
		{
			swap(heap[LC(id)] , heap[id]);
			down(LC(id));
		}
	}
}

void insert(__int64 t)
{
	heap[++size] = t;
	up(size);
}

__int64 dele()
{
	__int64 tmp = heap[top];
	if(RC(top) <= size)
	{
		if(heap[LC(top)] < heap[RC(top)])
		{
			tmp += heap[LC(top)];
			heap[LC(top)] = heap[size--];
			down(LC(top));
		}
		else
		{
			tmp += heap[RC(top)];
			heap[RC(top)] = heap[size--];
			down(RC(top));
		}
		heap[top] = tmp;
		down(top);
	}
	else
	{
		size --;
		tmp += heap[LC(top)];
	}
	return tmp;
}

void print(int num)
{
	int k = 1,cnt = 0,kk = 0;
	while(num)
	{
		num -= k;
		while(kk < k)
		{
			cnt ++; kk ++;
			cout<<heap[cnt]<<" ";
		}
		kk = 0;
		cout<<endl;
		k = min(k<<1, num);
	}
}

int main()
{
	__int64 sum = 0;
	freopen("./3253.in" , "r" , stdin);
	int n;
	cin>>n;
	if(n == 1)
	{
		cout<<0<<endl;
		return 0;
	}
	while(n--)
	{
		int t;
		scanf("%d",&t);
		insert(t);
	}
	while(size > 1)
	{
		sum+= dele();
	}
	cout<<sum<<endl;
	return 0;
}

STL偷懒版

/*
poj 3253
324K	32MS
*/
#include<queue>
#include<cstdio>
using namespace std;
priority_queue<int>myQueue;
int main()
{
	int n,t;
	__int64 ans = 0;
	scanf("%d",&n);
	for(int i = 1;i <= n;i ++)
	{
		scanf("%d",&t);t = -t;
		myQueue.push(t);
	}
	while(myQueue.size() > 1)
	{
		__int64 t1 = myQueue.top();
		myQueue.pop();
		__int64 t2 = myQueue.top();
		myQueue.pop();t1 += t2;ans += t1;
		myQueue.push(t1);
	}
	printf("%I64d\n",-ans);
	return 0;
}