2020-2021:teams:alchemist:nowcoder_weekly_41
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:alchemist:nowcoder_weekly_41 [2020/05/22 17:11] maxdumbledore |
2020-2021:teams:alchemist:nowcoder_weekly_41 [2020/05/22 18:44] (当前版本) maxdumbledore [F. Fuel Economy] |
||
|---|---|---|---|
| 行 24: | 行 24: | ||
| F应该是一道值得被记忆的贪心经典题！ | F应该是一道值得被记忆的贪心经典题！ | ||
| - | 我的想法其实有点绕，可能有更好的做法。我们如果知道到了第i个加油站，之前每个加油站的加油后的油量是多少。这个时候，我们会在此时加油到至少能到达下一站，如果需要油的话，我们会从之前能加并且最低的价格来加。什么时候能加？加的话之后的油量都会升高一个值，每个时刻都不能超过油箱容量。因此如果一个时刻已经加满，那么它之前的所有加油站都不能加油了， | + | 我的想法其实有点绕，可能有更好的做法。我们如果知道到了第i个加油站，之前每个加油站的加油后的油量是多少。这个时候，我们会在此时加油到至少能到达下一站，如果需要油的话，我们会从之前能加并且最低的价格来加。什么时候能加？加的话之后的油量都会升高一个值，每个时刻都不能超过油箱容量。因此如果一个时刻已经加满，那么它之前的所有加油站都不能加油了。另外，如果一个加油站距离当前加油站比另一个要远，而且还贵，那么该加油站永远都不会被选择，这是因为后者的可加油量一定会更大。 |
| + | 于是我们想到了维护一个单调递增的队列。并且在队列中某个元素没有余量时进行弹出。这里还有一个问题，怎么维护队列内部每个加油站的剩余油量呢？实际上由上一个性质，可以看出我们队列里面的油量是递减的（因为会优先选择队头加油），所以首先弹出的都是队头，并且我们只要将油量表示为（当前总加油值-距离）即可。 | ||
| + | |||
| + | ---by Max.D. | ||
| ===== K. Breed Assignment ===== | ===== K. Breed Assignment ===== | ||
| 其实是一道暴搜题，理论上是O(3^15*50)的，实际上可以剪枝优化。剪枝包括：去除重复出现的关系，将相同的奶牛用并查集进行合并，只对并查集中下标最小的奶牛进行搜索，其余的让其和这个奶牛相等即可。 | 其实是一道暴搜题，理论上是O(3^15*50)的，实际上可以剪枝优化。剪枝包括：去除重复出现的关系，将相同的奶牛用并查集进行合并，只对并查集中下标最小的奶牛进行搜索，其余的让其和这个奶牛相等即可。 | ||
2020-2021/teams/alchemist/nowcoder_weekly_41.1590138662.txt.gz · 最后更改: 2020/05/22 17:11 由 maxdumbledore
