CF 1166A Silent Classroom

传送门

题目大意

有 n ( n ≤ 100 ) n \pod{n \le 100} n(n≤100) 个学生，我们需要将这些学生分到两个班上。对于两名在同一班级的学生，如果他们的名字首字母相同，他们就会聊天。

现在给定这些学生的名字，问最少有多少对学生会在一起聊天。

思路

显然这些学生的名字并不重要，重要的是这些学生的名字的首字母，因此我们只需要保存以各字母为首字母的学生数量。

如果两个学生名字的首字母不同，显然他们永远不会对答案有贡献，因此分开考虑各首字母的同学们。对于一个有 x x x 个同学的首字母，设有 y y y 名同学分到教室一，有 x − y x - y x−y 名同学分到教室二，则这个首字母对答案的贡献为：
y ( y − 1 ) 2 + ( x − y ) ( x − y − 1 ) 2 \frac{y(y - 1)} {2} + \frac {(x - y)(x - y - 1)} {2} 2y(y−1)​+2(x−y)(x−y−1)​

展开得：
y 2 + ( x − y ) 2 − x 2 \frac {y^2 + (x - y)^2 - x} {2} 2y2+(x−y)2−x​

由均值不等式（的扩展），上式大于等于：
( y + x − y 2 ) 2 − x 2 (\frac {y + x - y} {2})^2 - \frac {x} {2} (2y+x−y​)2−2x​
当且仅当 y = x − y y = x - y y=x−y 时等号成立。

所以尽量对分就可以了。

别人的思路

贪心。考虑新来一个人，往首字母相同的人较少的教室走对答案的贡献小，所以尽量对分就可以了。

考了个高考思维方向都变了(╯‵□′)╯︵┻━┻

参考代码

n = int(input())
name = [None] * n
for i in range(n):
    name[i] = input()
buf = [0] * 26
for i in range(n):
    buf[ord(name[i][0]) - ord('a')] += 1

ans = 0
for i in range(26):
    part1 = buf[i] // 2
    part2 = buf[i] - part1
    ans += (part1 * (part1 - 1)) // 2 + (part2 * (part2 - 1)) // 2
print(int(ans))

Python 学习笔记

用 ord 函数获取一个字符的编码。

>>> help(ord)
Help on built-in function ord in module builtins:

ord(c, /)
    Return the Unicode code point for a one-character string.

整数除法始终用 //，不然肯定蹦出个浮点数。