1000ms

Difficulty: 3

所属公司 : 小米

时间 :2025年9月6日-开发

算法与标签>贪心算法

会员或题库专享

请先，开通会员或购买题库小米机考编程题库，可解锁完整内容。

购买小米机考编程题库开通会员

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（小米机考编程题库），可解锁完整内容。

购买题库开通会员

思路

将鞋按尺码分组（共有 $15$ 种尺码： $35\sim49$ ）。
对每个尺码：
- 先按颜色尽可能配对左/右同色对，得到价值 $p$ 的配对（贪心成立因为 $p \ge q$ ）。
- 剩余的左鞋总数与右鞋总数取最小值，做异色配对，得到价值 $q$ 的配对。
复杂度：时间 $O(n)$ ，空间 $O(n)$ 。

题目内容

小明家里有 $n$ 只鞋，他想出售这些鞋。

每只鞋区分左右，包含尺码，颜色两个属性、只有尺码相同的左鞋和右鞋凑成一双鞋才能够出售。

当两只鞋子的颜色相同时，一双鞋可以卖 $p$ 元，不相同时只能卖 $q$ 元。