老鼠进洞模型

老鼠进洞模型

最普通的一类老鼠进洞问题：

有n只老鼠，坐标分别为xi；有m个洞，有坐标yi，代价wi，容量ci。老鼠i进洞j的代价为|xi−yi|+wi|。每只老鼠必须进洞。

性质：老鼠和洞的匹配不相交

对于任意xi

现将老鼠和洞从左到右排序。

对老鼠和洞分别维护堆Q0和Q1，默认老鼠先去左边的洞。

1. 如果加入老鼠x

   在Q1中取出代价最少的，设代价为v,答案显然为x+v(这里的v显然是负数)

   老鼠反悔：在Q0中加入-（x+v)-x。

   解释：-(x+v)是将之前加入答案的值消去。-x是和后面洞的坐标y+此时老鼠的代价，那么实际上会变成y-x，表示下一段距离

2. 如果加入洞（y,w,c): (这里的w可有可不有，具体看题目条件)

   在容量被耗尽或者老鼠的代价不是负数时（这样的话必然是不优），重复从Q0中取出代价最少的老鼠，设这个代价为v。

   答案加上w(操作的权值) + y(这里的y和1中的-x刚好是|y-x|) + v(代价)

   1. 老鼠可能会选相比这个洞更后面的洞，在Q0加入-(w+y+v) (抵消上次操作贡献)-x(下一个洞和这次老鼠的对应距离)？

      实际不是。正确答案是-(w+y+v) (抵消上次操作贡献)+v(下一个洞和这次老鼠的对应距离，因为v可以继承之前几次的状态)

   2. 洞反悔去找更后面的老鼠，这时候在Q1中加入-(w+y+v)(抵消上次操作贡献)+w(每次进洞必要的)+y（与老鼠的坐标对应)?

      实际不是。因为这时候后面老鼠的坐标会大于这个洞，所用正确答案为-(w+y+v)(抵消上次操作贡献)+w(每次进洞必要的)-y（与老鼠的坐标对应)

   2中这两种情况不可能同时发生，不然一定能证明这是不优的。

总结：反悔其实是取消上一次答案的贡献+下次匹配自带的权值（正负取决如何满足绝对值定义)

#include 
using namespace std;
#define N 100005
#define ll long long
#define INF 2000000000
int n,m;
ll X[N];
ll Y[N],W[N],C[N];
ll ans;
struct info{
   ll v,cnt;};//v是反悔代价,cnt表示匹配了多少老鼠 
1
2
3
4
5
6
7
8
9
10
11