链接:
https://codeforces.com/problemset/problem/1551/C
题意:
女王只用abcde五个字母写一个有趣的故事,有趣的故事意为每个词的一个字母总和大于其他四个字母加起来的总和。给n个字符串,问最多能用几个字符串写一个有趣的故事。
本题就是求每一个字母在每个字符串中的权重,然后排序,从大到小求和,直到加和小于等于0。
代码如下:
#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
#include<string>
#include<string.h>
using namespace std;
typedef long long ll;
vector<int>w[5];
int main() {int T;cin >> T;while (T--) {int n;cin >> n;string s;for (int i = 0; i < n; i++) {cin >> s;int cnt[5] = { 0 };for (int j = 0; j < s.size(); j++) {cnt[s[j] - 'a']++;}for (int j = 0; j < 5; j++) {w[j].push_back(cnt[j] * 2 - s.size());}}int ans = 0;for (int i = 0; i < 5; i++) {sort(w[i].begin(), w[i].end());int sum = 0;int temp = 0;for (int j = n - 1; j >= 0; j--) {sum += w[i][j];if (sum > 0) {temp++;}else {break;}}if (temp > ans) {ans = temp;}}cout << ans;cout << endl;for (int i = 0; i < 5; i++) {w[i].clear();}}
}