Exam2019

1.字符串由“碎片”组成，每个碎片为单一字母组成，如：“aaabbccaddd” 由碎片 “aaa”,“bb”,“cc”,“a”,“ddd” 组成。
输入：一个字符串
输出：按字典输出碎片，每个碎片一行，相同的碎片只输出一次

C++

#include<bits/stdc++.h>
using namespace std;
int main()
{
	vector<string> v;
	string s,t;
	int i;
	cin>>s;
	t=s[0];
	for(i=1;i<s.size();i++)
	{
		if(s[i]==s[i-1])
		{
			t+=s[i];
		}
		else
		{
			v.push_back(t);
			t=s[i];
		}
	}
	v.push_back(t);
	sort(v.begin(),v.end());
	cout<<v[0]<<endl;
	for(i=1;i<v.size();)
	{
		if(v[i]==v[i-1])
		{
			i++;	
		}
		else
		{
			cout<<v[i]<<endl;
			i++;
		}	
	}
	return 0; 
}

2.求哈夫曼树的最短带权路径长度。
输入：第一行为权值个数 n ，第二行是 n 个权值
输出：最短带权路径长度

C++

#include<bits/stdc++.h>
using namespace std;
int main()
{
	vector<int> v;
	int n,t,sum=0;
	cin>>n;
	while(n--)
	{
		cin>>t;
		v.push_back(t);
	}

	
	
	while(v.size()!=1)
	{
		sort(v.begin(),v.end());
		t=v[0]+v[1];
		sum+=t;
		v.erase(v.begin(),v.begin()+2);
		v.push_back(t);
	}
	cout<<sum<<endl;
	return 0;
}