思路

• 将鞋按尺码分组（共有 $15$ 种尺码：$35\sim49$）。

• 对每个尺码：

  • 先按颜色尽可能配对左/右同色对，得到价值 $p$ 的配对（贪心成立因为 $p \ge q$）。
  • 剩余的左鞋总数与右鞋总数取最小值，做异色配对，得到价值 $q$ 的配对。

• 复杂度：时间 $O(n)$，空间 $O(n)$。

题目内容

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

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

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