#includelt;iostreamgt; #includelt;map

2018-09-26 21:27 吉林大学 C++

关注

#include<iostream> #include<map> #include<string> #include<set> using namespace std; int main() { string s; getline(cin, s); map<char, int> count; for (int i = 0;i < s.size();i++) { if (count.find(s[i]) != count.end()) { count[s[i]]++; } else count.insert(pair<char, int>(s[i], 1)); } map<int, set<string>> quanzhi; for (map<char, int>::iterator it = count.begin();it != count.end();it++) { string temp = ""; if (quanzhi.find((*it).second) != quanzhi.end()) { quanzhi[(*it).second].insert(temp + (*it).first); } else { set<string> temp1; temp1.insert(temp + (*it).first); quanzhi.insert(pair<int, set<string>>((*it).second, temp1 )); } } map<char,string> ans; while (quanzhi.size() > 1) { string temp = ""; int a1, a2; string s1, s2; map<int, set<string>>::iterator it = quanzhi.begin(); a1 =(*it).first; if ((*it).second.size() > 1) { s1 = *(*it).second.begin(); (*it).second.erase((*it).second.begin()); a2= (*it).first; s2= *(*it).second.begin(); (*it).second.erase((*it).second.begin()); } else { s1 = *(*it).second.begin(); (*it).second.erase((*it).second.begin()); it++; a2 = (*it).first; s2 = *(*it).second.begin(); (*it).second.erase((*it).second.begin()); } if (quanzhi[a1].size() == 0) { if (a1 == a2) { quanzhi.erase(a1); } else { quanzhi.erase(a1); if (quanzhi[a2].size() == 0) quanzhi.erase(a2); } } if (a1 < a2) { for (int i = 0;i < s1.size();i++) { if (ans.find(s1[i]) != ans.end()) { ans[s1[i]] = '0' + ans[s1[i]]; } else { ans.insert(pair<char, string>(s1[i], "0")); } } for (int i = 0;i < s2.size();i++) { if (ans.find(s2[i]) != ans.end()) { ans[s2[i]] = '1' + ans[s2[i]]; } else { ans.insert(pair<char, string>(s2[i], "1")); } } } else if (a1 > a2) { for (int i = 0;i < s1.size();i++) { if (ans.find(s1[i]) != ans.end()) { ans[s1[i]] = '1' + ans[s1[i]]; } else { ans.insert(pair<char, string>(s1[i], "1")); } } for (int i = 0;i < s2.size();i++) { if (ans.find(s2[i]) != ans.end()) { ans[s2[i]] = '0' + ans[s2[i]]; } else { ans.insert(pair<char, string>(s2[i], "0")); } } } else { if (s1.size() <= s2.size()) { for (int i = 0;i < s1.size();i++) { if (ans.find(s1[i]) != ans.end()) { ans[s1[i]] = '0' + ans[s1[i]]; } else { ans.insert(pair<char, string>(s1[i], "0")); } } for (int i = 0;i < s2.size();i++) { if (ans.find(s2[i]) != ans.end()) { ans[s2[i]] = '1' + ans[s2[i]]; } else { ans.insert(pair<char, string>(s2[i], "1")); } } } else { for (int i = 0;i < s1.size();i++) { if (ans.find(s1[i]) != ans.end()) { ans[s1[i]] = '1' + ans[s1[i]]; } else { ans.insert(pair<char, string>(s1[i], "1")); } } for (int i = 0;i < s2.size();i++) { if (ans.find(s2[i]) != ans.end()) { ans[s2[i]] = '0' + ans[s2[i]]; } else { ans.insert(pair<char, string>(s2[i], "0")); } } } } if (quanzhi.find(a1 + a2) != quanzhi.end()) { quanzhi[a1 + a2].insert(s1 + s2); } else { set<string> tee; tee.insert(s1 + s2); quanzhi.insert(pair<int, set<string>>(a1 + a2, tee)); } } for (int i = 0;i < s.size();i++) { cout << ans[s[i]]; } } 过了，但是代码挺垃圾的

查看原帖

1 评论