1 条题解
-
0
统计每个大写字母在字符串中出现的次数,然后每次遇到
*时,将其替换为当前出现次数最少的字母。可以用优先队列实现,也可以直接遍历 个字母查找。整体时间复杂度为 。代码:
#include <iostream> #include <string> #include <queue> #include <cstring> using namespace std; typedef long long ll; struct Item { int ch, freq; bool operator<(const Item &o) const { return freq > o.freq; } }; int main() { int cases; cin >> cases; while(cases--) { string str; cin >> str; int freq[26] = {}; int len = str.size(); priority_queue<Item> pq; for(int i=0;i<len;++i){ if(str[i]!='*') ++freq[str[i]-'A']; } for(int i=0;i<26;++i){ pq.push({i,freq[i]}); } for(int i=0;i<len;++i){ if(str[i]=='*'){ auto x=pq.top(); pq.pop(); ++freq[x.ch]; pq.push({x.ch,freq[x.ch]}); } } ll res=0; for(int i=0;i<26;++i) res+=1LL*(len-freq[i])*freq[i]; cout<<res/2<<'\n'; } }
- 1
信息
- ID
- 223
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 3
- 标签
- 递交数
- 2
- 已通过
- 1
- 上传者