题号

CodeForces - 922D

思路

s/h越大的越往前排，这样整体的字符串才是s/h值由大变小。

代码

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
52
53
54
55
#include<iostream>
#include<algorithm>
using namespace std;
const int MAX=100005;
struct T
{
	int sNum;
	int hNum;
	float sDh;
	int sh;
}tManager[MAX];
bool cmp(T a,T b)
{
	return a.sDh>b.sDh;
}
int main()
{
	int total,id=0;
	char str[MAX];
	cin>>total;
	while(id<total)
	{
	    cin>>str;
	    int i=0;
	    while(str[i]!='\0')
	    {
	    	if(str[i]=='s')
				tManager[id].sNum++;
	    	else if(str[i]=='h')
				{
	    	tManager[id].hNum++;
				tManager[id].sh+=tManager[id].sNum;
			  }
				i++;
	    }
			if(!tManager[id].hNum)
			{
				tManager[id].sDh=MAX;//s的数量与h的数量的比值最大有可能为99999；
				//所以用MAX就足够了
			}
			else
	    tManager[id].sDh=(float)tManager[id].sNum/tManager[id].hNum;
			id++;
	}
	sort(tManager,tManager+id,cmp);
  long long ans=0,sCot=0;//ans最大有可能是5w*5w，所以要用long long
  for(int i=0;i<id;i++)
	{
		ans+=sCot*tManager[i].hNum;
		ans+=tManager[i].sh;
		sCot+=tManager[i].sNum;
	}
   cout<<ans<<endl;
 
}