题目大意:
A和B各有n个pie。对于这2n个pie两人各自有一个可口程度的评估。两人交换pie,每次送出去的pie必须不比收到的pie难吃(从送礼人视角)。如果其中任意一个人送出的礼物在另外一个人的视角里可口程度为0,即交换结束。pie不可以重复交换。求A送出每一个pie时交换结束分别需要的最少步数(或-1)
题目解法:
抽象成最短路模型。f[i]表示送出第i个pie需要的最小步数。显然我们可以按照题意从一个i向其他f值进行转移。
再考虑到本题的一个特殊性,所有路径权值为1,因此可以使用bfs转移。显然,对于已经算出的值我们不需要重复计算。因此我们用multiset存储剩下的仍未计算的点,重载运算符分别按两种可口程度排序,每次转移的时候使用lower_bound定位,这样所有点都只会被访问一次。加上multiset和lower_bound的复杂度,最终复杂度是O(n log n)
Learning point:
活用set和重载运算符
对于dp不好处理的转移考虑最短路
对于权值为1的最短路使用bfs
[USACO 17Dec Gold] A Pie for a Pie
原文:https://www.cnblogs.com/myrcella/p/12130101.html