Codeforces 922D(贪心)

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

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

#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;
}