1000ms

Difficulty: 5

所属公司 : 美团

时间 :2024年9月21日

算法与标签>贪心算法

会员或题库专享

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

购买美团机考编程题库开通会员

会员专享

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

购买题库开通会员

思路

先假设所有物品都没有贴到“匹配标签”，此时总和为 $\displaystyle \text{base}=\sum_{i=1}^{n} c_i$ 。

若把某个物品 $i$ 贴上它匹配的 $a_i$ 号标签，总和会增加 $\displaystyle \Delta_i = b_i - c_i$ 。

由于每种标签只有 $1$ 张，对于同一标签种类 $t$ ，最多只能选择一个满足 $a_i=t$ 的物品来获得这次“增量”。为了使总和最大，我们对每个标签种类 $t\in[1,m]$ ，只需挑选该类下的最大增量

题目内容

小美正在给自己的物品贴标签。她一共有 $m$ 种不同的标签，每种标签只有一个。对于第 $i$ 个物品，如果贴上 $a_i$ 号标签，那么它的美观值为 $b_i$ ;如果没有贴上 $a_i$ 号标签，则其美观值为 $c_i$ 。小美想知道在合理的分配下，所有物品的美观值之和最大为多少。