当前位置: 代码迷 >> 综合 >> C - Interesting Story (cf)贪心
  详细解决方案

C - Interesting Story (cf)贪心

热度:80   发布时间:2023-11-23 05:59:23.0

原题链接:Problem - 1551C - Codeforces

之前也遇到过差不多的题,但是不太会写

参考了大佬的,写的很详细:


Interesting Story_夭辰的博客-CSDN博客

还是看贡献

遍历abcde每个字母,然后对于每个串,跟此时选择的字母相同的贡献为1,不相同的贡献为-1......

#include<iostream>
#include<cmath>
#include<vector>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
#define INF 0x3f3f3f3f
typedef pair<int, int> PII;
#define rep(i, n) for (int i = 1; i <= (n); ++i)
#define rrep(i, n) for (int i = m; i >= (1); --i)
typedef long long ll;const int N = 200010;
char c[5] = { 'a', 'b', 'c', 'd', 'e' };
int n;vector<int> v;
vector<string> s;bool comp(int a, int b) {return a > b;
}int main() {int t;cin >> t;while (t--) {cin >> n;for (int i = 1; i <= n; i++) {string s0;cin >> s0;s.push_back(s0);}int ans = 0;for (int i = 0; i < 5; i++) {char ch = c[i];v.clear();for (auto j : s) {int dif = 0;for (auto k : j) {if (k == ch) dif++;else dif--;}v.push_back(dif);}int sum = 0;sort(v.begin(), v.end(), comp);for (int j = 0; j < n; j++) {sum += v[j];if (sum <= 0) {ans = max(ans, j);break;}if (j == n - 1) ans = n;}if (ans == n) break;}cout << ans << endl;s.clear();}return 0;
}

之前一直报错说vector越界,我也不知道咋回事

之后把vector放在了外面就好了,所以以后还是把vector开在外面比较保险

这样的话一定要记得在每次while的最后的地方要clear

这个地方对于vector<int> v也记得在每次对于选择的一个字母,换另一个字母时也要clear

补充:

是我蠢了,之后发现是存s的时候越界了。。。