标签:贪心

OI

[POJ2431]Expedition[贪心,堆]

cgazn阅读(112)评论(0)赞(0)

题面 一开始想到一个错误策略: 每次在当前油量能走到的范围内找油最多的加油站…后面发现有可能会要在范围内多次加油才可能走到终点, 需要根据油量从大到小依次选择加油站, 于是容易想到用一个大根堆来维护所有可以走到的油站, 直到不能...

OI

[USACO09OCT]津贴Allowance[贪心]

cgazn阅读(112)评论(0)赞(0)

题面 首先面值大于$latex C$的硬币肯定只能直接计入答案. 剩下的硬币肯定要凑出尽可能接近$latex C$的面值, 策略是在面值不超过$latex C$的前提下优先使用大面值, 因为这样可以在使现在和将来避免浪费钱的前提下凑近$la...

OI

[POJ1017]Packets[贪心]

cgazn阅读(116)评论(0)赞(0)

题面 题意: 要用尽量少的6*6的箱子放入一些1*1~6*6的物品, 设他们分别有$latex a_i$个. 首先答案至少要$latex a_6+a_5+a_4$这么多, 因为他们是不能多个并存的. 然后对于5*5和4*4的物品我们就可以贪...

OI

[HDU6095]Rikka with Competition[贪心]

cgazn阅读(115)评论(0)赞(0)

题面 感觉这题最水… 显然$latex a$越低就越难赢, 而只要每次比赛$latex a$之差都在$latex k$内就可以赢. 所以每个人都要尽量和第一个$latex a$比它大的人比, 如果在n-1场比赛中有一场$late...

OI

[洛谷P1080]国王游戏[贪心,高精]

cgazn阅读(115)评论(0)赞(0)

题面 贪心策略: 按照每个大臣左右手的乘积升序排列为最优解. 这可以采用临项交换的方法证明, 常见于涉及以某关键字排序的贪心策略.设第$latex i$个人左手为L[i], 右手为R[i], 国王为第0个人, 则: 考虑对一对临项$late...

OI

[POJ1328]Radar Installation[贪心]

cgazn阅读(84)评论(0)赞(0)

题面 首先这道题容易想到降维, 一个点P(x, y)能够被圆心O在X轴上的一个圆覆盖, 等价于O在线段[$latex x-\sqrt{r^2-y^2}$, $latex x+\sqrt{r^2-y^2}$]上. 这样就转化为要用最少的点标记...

OI

[POJ3190]Stall Reservations[贪心]

cgazn阅读(83)评论(0)赞(0)

题面 首先要把牛按照开始时间升序排序, 不然安排一头牛时这头牛开始时间之前我们都管不了了, 可能造成浪费一段正好可以安排后面一头开始时间更早的牛的空档. 而按开始时间排序后就能线性的安排每头牛, 保证安排到每一头牛时这头牛的开始时间之前已经...