Codeforces 922D(贪心)

Codeforces 922D
题意:已知n个字符串只含s和h 对着n个字符串进行排序组成新的一串字符 使得新字符串中子序列是sh的数目最多

贪心,s自然要放在前面,所以s比重大的字符串要放在前面,差值是不行的

Codeforces Submission

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<cmath>
#include<set>
#include<iostream>
using namespace std;
#define ms(i, j) memset(i, j, sizeof i)
#define ll long long
#define db double
int n;
struct data {
string s;
int ns, nh;
double cha;
bool operator < (const data &b) const {
return cha > b.cha;
}
}t[100000 + 5];
string ss;
void clean() {
}
int solve() {
clean();
for (int i = 1; i <= n; i++) {
cin >> t[i].s;
int len = t[i].s.length();
t[i].ns = 0, t[i].nh = 0;
for (int j = 0; j < len; j++) {
if (t[i].s[j] == 's') t[i].ns++; else if (t[i].s[j] == 'h') t[i].nh++;
}
if (t[i].nh == 0) t[i].cha = 1e11;
else t[i].cha = (db)t[i].ns / (db)t[i].nh;
}
sort(t + 1, t + 1 + n);
for (int i = 1; i <= n; i++) ss += t[i].s;
int len = ss.length();
ll ans = 0, ns = 0, nh = 0;
for (int i = 0; i < len; i++) {
if (ss[i] == 's') ns++;
if (ss[i] == 'h') nh++, ans += ns; else nh = 0;
}
printf("%I64d\n", ans);
return 0;
}
int main() {
cin >> n, solve();
return 0;
}

------ 本文结束 ------