safe or unsafe

链接

这题要求我们对WPL(带全路径长度)进行计算,而WPL就等于每个子节点相加后形成的加权节点的总和,比如有四组数据出现的频率分别是1 2 3 4

那么加权节点的值分别为1+2=3,3+3=6,6+4=10,总和为19

直接计算WPL=3x(1+2)+2x3+1x4=19

二者相等,依据这个就好处理了

考虑使用map统计频率,用优先队列来进行计算

#include<bits/stdc++.h>
using namespace std;
int main() {
	int n;cin >> n;
	for (int i = 0;i < n;i++) {
		int setWPL;
		int WPL = 0;
		cin >> setWPL;
		string str;
		cin >> str;
		map<char, int>freq;
		for (char ch : str) {
			freq[ch]++;
		}
		priority_queue<int,vector<int>,greater<int>> tree;
		for (const auto& it : freq) {
			tree.push(it.second);
		}
		if (tree.size() == 1) {
			WPL = tree.top();
		}
		while (tree.size()>1) {
			int a, b;
		
			a= tree.top();
			tree.pop();
			b= tree.top();
			tree.pop();
			tree.push(a + b);
			WPL += (a + b);
		}
		
		if (WPL <= setWPL) {
			cout << "yes" << endl;
		}
		else {
			cout << "no" << endl;
		}

	}
}

时间复杂度:O(n)

空间复杂度:O(n时间复杂度：O(n × (m + k log k))

n：测试用例数量

m：每个字符串长度

k：字符串中不同字符数量

空间复杂度：O(m + k)