题目描述
亚马逊购物定期推出优惠活动来吸引更多的顾客。最近,它为库存中的n个物品推出了一项优惠,其中第i个物品为购买该物品的顾客提供了奖励点数。每次购买一个有优惠的物品时,顾客将获得与该物品相关联的奖励点数。然后,剩余物品的奖励点数会减少1,除非它将点数减少到0以下。
问题:找出通过最佳购买物品的方式可以获得的最大奖励点数。
注意:每个物品最多只能购买一次,换句话说,在购买第h个物品后,奖励点数变为0。
示例:
假设物品数量为n=5,它们的奖励点数为reward=[5, 2, 2, 3, 1]。可以按照以下方式购买物品:
购买第3个物品,奖励点数为2,剩余物品的奖励点数为[4, 1, 0, 2, 0]。
购买第4个物品,奖励点数为2,剩余物品的奖励点数为[3, 0, 0, 0, 0]。
购买第1个物品,奖励点数为3,剩余物品的奖励点数为[0, 0, 0, 0, 0]。
通过最佳购买物品的方式,总共可以获得的最大奖励点数为2+2+3=7。
思路
这道oa给的例子让人很困惑。正常来想肯定是选最大的奖励点拿,然后其他奖励点就会减一点。如果按照给出的例子想那么就会被绕进去。正确的想法是贪心,拿第一次剩余所有奖励点减1,拿第二次剩余所有物品奖励点减2…
代码
long getMaximumRewardPoints(vector<int> reward) {
long points = 0;
sort(reward.begin(), reward.end());
int cur = reward.size() - 1;
for (int i = 0; i < reward.size(); i++) {
points += max(0, reward[cur] - i);
cur -= 1;
}
return points;
}