CF 461 D
CF 461 D
作为D题来说是比较水的了，但是最后因为最后答案用int存不开，所以在比赛时并没有A掉。
题解
题目要求给出指定个由s和h组成的字符串，怎样将这些字符串排列可以使得sh对最多。一个sh对存在当且仅当s的下标在h前。最后只需输出sh对的数目即可。
因此，我们可以发现最终的ans的求解可以分为两部分:
当s和h在同一个字符串内时，无论字符串如何排列，其构成的sh对的数目不变，所以我们只需在读入时处理出来这些数值即可。
当s和h不再同一个字符串内时。对于两个字符串Str1和Str2,其之间产生的sh对的数目为$Str1.s Str2.h \(或\) Str2.s Str1.h \((`.s`为字符串中`s`的数目,`.h`亦然)。这样，我们可以通过比较这两个数值的大小来确定`Str1`与`Str2`的顺序。而对于更多数目的字符串，同理。所以我们只需要对所有的字符串按照\) $的降序排列即可。
代码
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 <iostream>
#include <algorithm>
char s[100100];
struct Cnt
{
trueint s;
trueint h;
trueconst bool operator < (const Cnt& tmp)const{
truetruereturn (long long)s*tmp.h > (long long)tmp.s*h;
true}
}cnt[100100];
int main()
{
truelong long ans = 0;
trueint n;
truescanf("%d",&n);
truefor (int j = 0; j<n; j++)
true{
truetruestd::cin >> s;
truetruecnt[j].s = 0;
truetruecnt[j].h = 0;
truetruefor (int i = 0; s[i]!='\0'; i++)
truetruetrueif (s[i]=='h')
truetruetrue{
truetruetruetrueans += cnt[j].s;
truetruetruetruecnt[j].h++;
truetruetrue}else if (s[i]=='s'){
truetruetruetruecnt[j].s++;
truetruetrue}
true}
truestd::sort(cnt,cnt+n);
truelong long t = 0;
truefor (int i = 0; i<n; i++)
true{
truetrueans += t*cnt[i].h;
truetruet += cnt[i].s;
true}
truestd::cout << ans;
}
|