test-for-git/cg/tree/tree02.cpp

/*
 * tree02.cpp
 *
 *  Created on: Apr 12, 2024
 *      Author: 28032
 */


//创建树的方法
/*#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Note
{
	Note():value(0),left(NULL),right(NULL),isleaf(false){}
	Note(int val,bool is)
	{
		value = val;
		left = NULL;
		right = NULL;
		isleaf = is;
	}
	Note(int val,Note* l,Note* r)
	{
		value = val;
		left = l;
		right = r;
		isleaf = false;
	}

	int value;
	Note* left;
	Note* right;
	bool isleaf;
};

bool cmp(const Note* a,const Note* b)
{
	return a->value<b->value;
}

//void S_insert(vector<Note*>& arr,Note* in,int l,int r,int mid)
//{
//	if(in->value>arr[mid]->value)
//	{
//		S_insert(arr,)
//	}
//}

void buildTree(vector<Note*>& arr)
{
	while(arr.size()>1)
	{
		Note* t = new Note(arr[0]->value+arr[1]->value,arr[0],arr[1]);
		arr.push_back(t);
		arr.erase(arr.begin(),arr.begin()+2);
		sort(arr.begin(),arr.end(),cmp);
	}
}

void getMinWPL(Note* root,int l,int &WPL)
{
	if(root == NULL)	return ;

	getMinWPL(root->left,l+1,WPL);
	getMinWPL(root->right,l+1,WPL);
	if(root->isleaf)
		WPL += root->value*l;
}

int main()
{
	while(1)
	{
		int n = 0,
			WPL = 0;

		cin>>n;
		if(n == 0)	break;

		vector<Note*> arr;
		for(int i = 0;i < n;i++)
		{
			int temp = 0;
			cin>>temp;
			Note* t = new Note(temp,true);
			arr.push_back(t);
		}
		sort(arr.begin(),arr.end(),cmp);

		buildTree(arr);
		getMinWPL(arr[0],0,WPL);

		cout<<WPL<<endl;
	}


	return 0;
}*/


//不建树
/*
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
	int n = 0;

	while(1)
	{
		cin>>n;
		if(n == 0)	break;

		vector<int> in;
		int wpl = 0;

		for(int i = 0;i < n;i++)
		{
			int tmp = 0;
			cin>>tmp;
			in.push_back(tmp);
		}

		while(in.size() > 2)
		{
			sort(in.begin(),in.end(),greater<int>());
			int t1 = in.back();
			in.pop_back();
			int t2 = in.back();
			in.pop_back();
			wpl+=(t1+t2);
			in.push_back(t1+t2);
		}

		wpl+=(in[0]+in[1]);
		cout<<wpl<<endl;
	}



	return 0;
}
*/