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)