题目分析

观察数据范围 \(n \leq 10^5\), 还有 "任意顺序连接" 及 "最大化" 的要求, 自然想到了做法 : 邻项交换

考虑相邻的两个位置 \(i\) 与 \(j = i + 1\), 他们的相对顺序不会影响 \([1, i - 1]\) 及 \([j + 1, n]\) 这些位置的答案. 所以只需要考虑 \(i, j\) 之间的贡献.

1. 当 \(i\) 在 \(j\) 之前, \(i, j\) 之间的贡献应为 : \(countS ( \ Str(i) \ ) * countH ( \ Str(j) \ )\)
2. 当 \(j\) 在 \(i\) 之前, \(i, j\) 之间的贡献应为 : \(countS ( \ Str(j) \ ) * countH ( \ Str(i) \ )\)

只需比较以上两式之间的大小就能确定 \(i, j\) 之间的相对顺序. 由于这满足严格弱序, 可以扩展到全局.

把式子写成 \(Cmp()\) 就能用 \(std::sort()\) 以 \(O(nlogn)\) 求出最优的排列顺序.

统计答案非常简单, \(O(n)\) 扫一遍即可.

细节请看代码.

代码实现

#include <cstdio>
#include <string>
#include <iostream>
#include <algorithm>

const int N = 1e5;

int n;
std::string Str[N + 5];

struct Node { int S1, S2, Id; } Q[N + 5];

bool Cmp (Node, Node);

int main() {
	std::ios::sync_with_stdio (false);

	std::cin >> n;
	for (int i = 1; i <= n; ++i) {
		std::cin >> Str[i];
		int Len = Str[i].length();
		for (int j = 0; j < Len; ++j)
			Q[i].S1 += (Str[i][j] == 's'), Q[i].S2 += (Str[i][j] == 'h');
		Q[i].Id = i;
	
	} std::sort (Q + 1, Q + 1 + n, Cmp);
	
	auto NowS = 0ll, Ans = 0ll;
	for (int i = 1; i <= n; ++i) {
		int Len = Str[Q[i].Id].length();
		for (int j = 0; j < Len; ++j) {
			char tap = Str[Q[i].Id][j];
			if (tap == 's') ++NowS;
			else Ans += NowS;
		}
	} printf ("%lld\n", Ans);
	return 0;

} bool Cmp (Node X, Node Y) {
	return 1LL * X.S1 * Y.S2 > 1LL * Y.S1 * X.S2;
}