题解 | #HDU2527#

哈夫曼树

#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<string>
#include<cstdio>
#include<queue>
using namespace std;
int main()
{
	priority_queue<int, vector<int>, greater<int>>q;//小优先队列
	string s;
	int t = 0;
	int n = 0;
	scanf("%d", &t);
	for (int i = 0; i < t; i++)
	{
		scanf("%d", &n);
		cin >> s;
		sort(s.begin(), s.end());
		int num = 1;
		for (int j = 1; j <= s.length(); j++)//统计频数
		{
			if (s[j] != s[j - 1])
			{
				q.push(num);
				num = 1;
			}
			else
			{
				num++;
			}
		}
		int ans = 0;
		if (q.size() == 1)
		{
			ans = s.length();
		}
		while (q.size() > 1)
		{
			int a = q.top();
			q.pop();
			int b = q.top();
			q.pop();
			ans += a + b;//计算长度
			q.push(a + b);
		}
		
		q.pop();
		if (ans <= n)//进行比较
		{
			printf("yes\n");
		}
		else
		{
			printf("no\n");
		}
	}
	return 0;
}