题意
给定$n$个二元组$(x_i,y_i)$和另外$m$个二元组$(a_i,b_i)$。
你可将$(a_j,b_j)$与$(x_i,y_i)$匹配,需要满足$a_j \leq x_i$且$b_j \leq y_i$。每个$(a_i,b_i)$和$(x_i,y_i)$都至多可以进行1次匹配。
求解最大匹配数,以及最大匹配数下最大总价值。
总价值的计算公式为,对于被分配的$(a_i,b_i)$,对$500a_i + 2b_i$求和。
$1 \leq n,m\leq10^5,0 < x_i,a_i < 1440 , 0 \leq y_i,b_i \leq100$
题解
先考虑最大匹配数的求解。注意到这是个二维偏序问题,考虑通过排序处理掉1维。
简单地,考虑将$(a_i,b_i)$和$(x_i,y_i)$按照第1维从小到大排序。基于此,对于1个$(a_i,b_i)$,容易通过二分查找到第1个$x_{id} \geq a_i$,则对于$j \in [id,n]$,均可满足$x_j \geq a_i$;对于$j \in[id,n]$,只要$y_j \geq b_i$即合法。
注意到,每个$(a_i,b_i)$和$(x_i,y_i)$都至多可以进行1次匹配;哪个二元组进行1次匹配贡献均为1,故只要依照 先选择范围窄的 后选择范围宽的 的原则,即可做到总匹配数最大化。
考虑两个二元组$(a_i,b_i)$和$(a_j,b_j)$,满足$a_i > a_j$,则一定有$id_i \geq id_j$,即只考虑第1维时,前者的选择范围被后者完全包含。此时我们优先考虑$(a_i,b_i)$,且执行策略使得此次选取对后续影响最小:选择$[id_i,n]$内$y$大于$b_i$的元素中$y$最小的那个。
你可能会想,同时考虑第2维时,$i$的选择范围也可能比$j$广,此时优先考虑$i$是否一定最优?反证法。假设不是最优,当且仅当,原本$(a_i,b_i)$选择$(x_k,y_k)$后$(a_j,b_j)$不能选择,但令$(a_i,b_i)$选择$(x_{k’},y_{k’})$($y_{k’}$ > $y_k$)后,$(a_j,b_j)$选择$(x_k,y_k)$。由原情况可得,除$(x_k,y_k)$外,不存在二元组$(x_1,y_1)$满足$x_1 \geq a_j,y_1 \geq b_j$;由改变后情况可得,存在除$(x_k,y_k)$的二元组$(x_{k’},y_{k’})$满足$x_{k’} \geq a_i >a_j,y_k’ > y_k \geq b_j$,与已知条件矛盾,故该假设不成立。
在此基础上,考虑最大化$\sum500a_i + 2b_i$,$0 < x_i,a_i < 1440 , 0 \leq y_i,b_i \leq100$。
对于$a_i$相同的元素,保证按照$b_i$从大到小排序即可;对于$a_i$不同的元素,考虑$b_i$的不同带来的最大影响:$500a_i$的变化量至少为500,$2b_i$变化量至多为200,故显然$b_i$不影响$a_i$从大到小取的策略。
总结算法流程:将$(a_i,b_i)$以$a_i$为第1关键字,$b_i$为第2关键字从大到小排序;$(x_i,y_i)$按照$x_i$从大到小排序。对于$(a_i,b_i)$,将合法的$y_i$放入1个$multiset$中;并在$multiset$中查找$b_i$的后继,若查找成功则计数并删除。
时间复杂度:$O(nlogn)$。代码见此