AC 10题,Rank 3th
我个人认为自己很差劲的地方还是补题方面,这一场截至5月22日我仍然没有进行补题,包括之前训练的那些场我的补题习惯并不良好。
以后我会督促自己,每天最最少化半个小时时间进行补题。
过的人不多但是其实是没啥好说的一道模拟题,注意细节即可,感觉这题写的还不错。
—by Max.D.
F应该是一道值得被记忆的贪心经典题!
我的想法其实有点绕,可能有更好的做法。我们如果知道到了第i个加油站,之前每个加油站的加油后的油量是多少。这个时候,我们会在此时加油到至少能到达下一站,如果需要油的话,我们会从之前能加并且最低的价格来加。什么时候能加?加的话之后的油量都会升高一个值,每个时刻都不能超过油箱容量。因此如果一个时刻已经加满,那么它之前的所有加油站都不能加油了。另外,如果一个加油站距离当前加油站比另一个要远,而且还贵,那么该加油站永远都不会被选择,这是因为后者的可加油量一定会更大。
于是我们想到了维护一个单调递增的队列。并且在队列中某个元素没有余量时进行弹出。这里还有一个问题,怎么维护队列内部每个加油站的剩余油量呢?实际上由上一个性质,可以看出我们队列里面的油量是递减的(因为会优先选择队头加油),所以首先弹出的都是队头,并且我们只要将油量表示为(当前总加油值-距离)即可。
—by Max.D.
其实是一道暴搜题,理论上是O(3^15*50)的,实际上可以剪枝优化。剪枝包括:去除重复出现的关系,将相同的奶牛用并查集进行合并,只对并查集中下标最小的奶牛进行搜索,其余的让其和这个奶牛相等即可。
注意,并查集的合并方式是从根的下标大的,连接到根的下标小的。这样才满足算法。写的过程中好几次zz了。
最zz的还有并查集忘了路径压缩,沃德天!一定不要犯这种低级错!
—by Max.D.
水题
—by Max.D.