wa,蒟蒻求调,滚动数组,样例已过
查看原帖
wa,蒟蒻求调,滚动数组,样例已过
1071516
isop楼主2024/5/14 18:25
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn=55;

inline int read()
{
	int a=0,f=1;
	char c=getchar();
	while(!isdigit(c))
	{
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c))
	{
		a=(a<<1)+(a<<3)+(c^'0');
		c=getchar();
	}
	return a*f;
}

void reflect(ll map[][maxn],int num,ll tmp)//滚动数组初始化
{
	for(int i=0;i<num;i++)//num当前层的点数 
	{
		if(map[0][i]==0) map[0][i]=tmp;
	}
}

void haffman(ll map[][maxn],int num)//向上一层求权值 
{
	for(int i=0;i<num;i+=2)//num表示当前层节点数 
	{
		map[1][i/2]=(map[0][i]+map[0][i+1]);
	}
}

int main()
{
	int len;
	while(cin>>len)
	{
		int a[maxn]={},maxdeep=0;//a每层节点数 
		ll tmp=1;//上一层最大元素
		ll map[2][maxn];//权值滚动数组 
		for(int i=1;i<=len;i++)//层序号从1开始
		{
			int x=read();
			maxdeep=max(x,maxdeep);
			a[x]++;
		}
		
		for(int i=0;i<a[maxdeep];i++)//手动 初始化+向上求值 最深层  节点序号从0开始 
		{
			map[0][i]=tmp;
		}
		sort(map[0],map[0]+a[maxdeep]);
		tmp=map[0][a[maxdeep]-1];
		haffman(map,a[maxdeep]);
		int relength=a[maxdeep];

		for(int i=maxdeep-1;i>0;i--)
		{
			memcpy(map[0],map[1],a[i+1]*sizeof(int));//浅层覆盖深层 
			
			int length;//长与原长 
			if(relength/2>=2 && relength/2>=a[i]) length=relength/2;
			else if(relength/2<=2 && relength/2>=a[i]) length=relength/2+1;
			else length=a[i];
			
			reflect(map,length,tmp);//补足节点权值

			sort(map[0],map[0]+length);
			tmp=map[0][length-1];
			haffman(map,length);
		}
		cout<<map[1][0]<<endl;
	}
}
2024/5/14 18:25
加载中...