hdu6326如何运用贪心、并查集和优先队列解决？

本文共计1670个文字，预计阅读时间需要7分钟。

题目：英雄王国的节操（根节点），对每个叛逆者，打他需要消耗a[i]HP，打完会获得b[i]HP，这些叛逆者会形成父子关系，即必须先打完父亲才能打儿子，重复的叛逆不用再打，问打完所有叛逆所需的最少HP。

题意：英雄在1节点（根节点），对每只怪，打他需要消耗a[i]HP，打完会获得b[i]HP，且这些怪会形成父子关系，即必须打完父亲才能打儿子，重复的怪不用再打，问打完所有怪所需要的最小HP

跑得贼慢。。。

感觉是少了一些基础。。所以只能照着题解做。。

首先需要考虑没有父亲关系限制的情况。。那就是要求出一个打怪的顺序了。。

考虑已经求出最优顺序，那么对2个相邻的怪来说，如果当前有t HP，那么经过这2关前的HP要求为t-a[i]>0和t-a[i]+b[i]-a[i+1]>0，如果这2个交换顺序则变成t-a[i+1]>0和t-a[i+1]+b[i+1]-a[i]>0显然前一个条件要比后一个条件要松。。结合2个条件分别减一下可以得到：max{a[i],a[i]+a[i+1]-b[i]}<max{a[i+1],a[i+1]+a[i]-b[i+1]} 设为式①

然后应优先选择a<b的，打怪的时候肯定要把能赚到的HP先拿到再来用于亏本的消耗。。