POJ - 3253 Fence Repair解题报告

排序aO(nlogn)+每次连接都需要维护（？）*连接n次。可见？不能大于n级别。想想？能不能是logn。 关键在于两个木板连接之后，如何找到新的木板应该在的位置。要是用链表存这些数，就只能用遍历查找，时间复杂度为O(n)这就超时了，要是用数组存着些数，那么虽然可以用二分查找了，但是找到之后插入极为不方便，也不行。这里就需要一种新的数据结构了。该数据结构要保证，删除，查找，插入及维护都是logn级别。原本以为haffman树可以做到，然后发现，建立的过程就是O(n^2)。那就只能是用n^2的复杂度了。 

#include<iostream>
#include<math.h>
#include<stdio.h>
#include<algorithm> 
#define N 60500
using namespace std;
struct ban
{
	long long int v;
	int next;
}a[N]={0};
int l[N]={0};
int n;
int m;
long long int sum=0;
int start=1;//起点记录为start
void build()
{
	for(int i=1;i<=n;i++)
	{
		a[i].v=(long long)l[i];
		a[i].next=i+1;
	}
	a[n].next=0;
}
void add()
{
	long long int l=a[start].v+a[a[start].next].v;//最小的两个合并
	//cout<<a[start].v<<" "<<a[a[start].next].v<<endl;
	start=a[a[start].next].next;
	sum=sum+l;
	//cout<<start<<" "<<l<<"  ";
	int u=start;
	//cout<<u<<" "<<l<<"    ";
	int last=-1;
	while(u!=0)
	{
		//cout<<l<<a[u].v<<endl;
		if(l<=a[u].v)//把l***去 
		{
			if(last==-1) start=m;
			else a[last].next=m;
			a[m].v=l;
			a[m].next=u;
			return;
		}
		last=u;
		u=a[u].next;
		//cout<<u<<last<<endl;
	}
	a[m].v=l;
	a[m].next=0;
	a[last].next=m;
}
void ceshi1()
{
	for(int i=1;i<=n;i++)
	{
		cout<<a[i].v<<" "<<a[i].next<<"     ";
	}
}
void ceshi2()
{
	int u=start;
	while(a[u].next!=0)
	{
		cout<<a[u].v;
		u=a[u].next;
	}
	cout<<endl;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&l[i]);
	}
	sort(l+1,l+n+1);
	//ceshi1();
	build();
	//ceshi1();
	m=n+1;
	for(int i=0;i<n-1;i++)//进行n-1次的合并 
	{
		add();
		m++;
		//ceshi2();
	}
	cout<<sum;
}

这里有去看了一下别人的聊天板，只有一块木板的时候，好像测是数据并不存在这种情况，其实我是觉得应该输出0的。

第一次写这个类似于链表的东西，各种各种插入测试语句，终于过了。。。。