#3738. 晶晶挑班服

晶晶挑班服

题目描述

校运会前,晶晶在服装店给班里挑班服。货架上有 n 件不同款式的样衣,每件样衣标着价格和尺码。晶晶的班级需要两件样衣:一件给男生,一件给女生。

她先记下每件样衣的价格和尺码(尺码用一个大写字母表示)。为了让两件衣服都合适,她要求两件样衣的尺码不同。在所有尺码不同的样衣组合中,她想挑出两件价格之和最小的一对。

例如货架上有 3 件样衣:价格 30 尺码 M、价格 50 尺码 S、价格 20 尺码 M。尺码不同的组合只有 (30,M) 和 (50,S),以及 (50,S) 和 (20,M),价格之和分别是 80 和 70,所以晶晶会选后者。

请问晶晶最少要花多少钱才能买到尺码不同的两件样衣?

输入格式

第一行一个整数 n(2 ≤ n ≤ 100),表示样衣数量。 接下来 n 行,每行一个整数 p 和一个大写字母 c,表示一件样衣的价格和尺码,中间用一个空格隔开(1 ≤ p ≤ 1000)。 保证至少存在两件尺码不同的样衣。

输出格式

输出一个整数,表示尺码不同的两件样衣的最小价格之和。

样例

3
30 M
50 S
20 M
70 
4
10 A
20 B
15 A
30 C
30 

说明/提示

数据范围:2 ≤ n ≤ 100,1 �� p ≤ 1000,尺码为大写字母。 提示:可以枚举任意两件样衣,检查尺码是否不同,再取价格和的最小值。

解析

解题思路

题目要求从 nn 件样衣中选出两件,满足尺码不同,并使价格之和最小。

最直接的做法是枚举所有可能的样衣对。对于每一对 (i,j)(i,j),如果两件样衣的尺码不同,就计算价格和,并更新最小值。由于 n≤100n \le 100,总对数最多为 (1002)=4950\binom{100}{2}=4950,枚举完全可行。

另一种思路是按尺码维护最小价格,但本题数据规模很小,直接枚举更简单,也不容易出错。

算法选择理由

  • 数据范围只有 n≤100n \le 100,双重循环的时间开销极小。
  • 题目只要求尺码不同,没有其他复杂约束,直接枚举所有两件组合即可覆盖所有合法方案。
  • 不需要排序或使用复杂数据结构,代码实现简单,正确性直观。

复杂度分析

  • 时间复杂度:O(n2)O(n^2),因为枚举所有样衣对。
  • 空间复杂度:O(n)O(n),用于存储每件样衣的价格和尺码。

在 n≤100n \le 100 的情况下,O(n2)O(n^2) 远小于时间限制,可以轻松通过。

来源

AI 生成 · 云端大模型(域):deepseek-chat · 入门 · 枚举