CF2209A Flip Flops

链接：Problem - A - Codeforces

题面

给你 n 只怪物，第 i 只怪物战力为 a[i]，你初始战力为 c，并且有 k 只拖鞋。你可以重复做两种操作：

1. 如果某只还活着的怪物满足 a[i] <= c，你可以击杀它，之后你的战力变成 c + a[i]。
2. 你可以对某只还活着的怪物扔一只拖鞋，这只拖鞋会坏掉，同时该怪物战力变成 a[i] + 1。

你的目标是：通过最优操作，使战斗结束时自己的战力 c 最大。 每组数据输出这个最大值。

数据范围：

• 1 <= t <= 500
• 1 <= n <= 100
• 0 <= c, k <= 10^9
• 0 <= a[i] <= 10^9

思路

双指针+贪心思想，给怪排序，先找到无法击杀的怪的位置，然后开始给当前能击杀的最高的怪喂拖鞋，尽量喂到和自己一个战力，然后杀这只怪再看后面的怪能不能击杀，如果能击杀就喂拖鞋，还是尽量喂到和自己一个战力后击杀，尽可能把拖鞋喂完。每次选择当前能击杀的最高战力。所以这题也应该可以用二分（没试过）每次查找当前能击杀最高战力的怪。二分复杂度就是nlogn，双指针就是O（n）

复杂度

O（n）

反思

一开始没理解对，以为杀怪也要拖鞋，那样就很复杂了，要先理解题目再对题目建模