1178 H. Stock Exchange

题意:
有(2n)只价值随时间线性变化的股票,即价值为(a_it+b_i(i=1,cdots,n)).初始时刻持有(1)到(n)各一份,在整数时刻可多次交易,每次交易可将一份股票换成在当前价值更低的任意一份,可以同时持有多份同种股票,目标是持有(n+1)到(2n)各一份.求最少所需时间和在此时间下最少所需交易次数.
题解:
首先考虑能否归约到只有初始时刻(0)和结束时刻(T)进行操作而不增加交易次数.
用调整法:
假设在除初始时刻(0)和结束时刻(T)的时刻(t)有一次(i o j)的交易:

如果时刻(t)有(j o k)或(k o i)的交易,可以合并并减少一次交易次数.
如果(a_igeq a_j),那么此后(i)的价值会一直比(j)高,
2.1. 如果后来还有(j o k)的交易,那么不妨在后面再进行(i o k)的交易可以减少一次交易次数.
2.2. 如果后来没有任何(j o k)的交易,说明(j)是最后需要持有的股票,不妨等到(T)时刻交易而不改变交易次数.
如果(a_i< a_j),和2同理可以向前合并,或调整到(0)时刻交易.

因此可以考虑只在时刻(0)和时刻(T)交易.

然后考虑如何确定结束时刻(T)的值.可以证明在时刻(0)先将每一份股票都尽可能换成T时刻的最贵股票,接着在时刻(T)再替换成对应的目标股票,不会影响正确性:把每一份股票(i(ileq i leq n))看成是独立地变成(j(n+1leq j leq 2n)),如果(i)是在时刻(0)变成(j),也就是说(i)能变成的"T时刻的最贵股票"至少在(T)时刻比(j)贵,因此无论(i)是如何变换到(j),都可以用上述方法变换.因此可以在(O(nlog nlog T_{max}))的时间求出(T).这里的(T_ ext{max})其实就是(b_ ext{max}),因为两条直线的交点横坐标不会超过(b_ ext{max}).

最后考虑如何求交易次数,可以用费用流解决这个问题,假设给定时刻(T),用(u_i)表示(0)时刻的(i)号股票,(v_i)表示(T)的(i)号股票.

源点向(u_i(1leq ileq n))连费用为(0)流量为(1)的边.
如果(b_igeq b_j,u_i)向(u_j)连费用为(1)流量无限的边.
(u_i)向(v_i)连费用为0流量无限的边.
如果(a_iT+b_igeq a_jT+b_j,v_i)向(v_j)连费用为0流量无限的边.
(v_i(n+1leq ileq 2n))向汇点连费用为(0)流量为(1)的边.

但这样会有(O(n^2))条边,需要优化建图,需要修改(2)和(4)的建边.
2'. (u_i)会向(u'_i)连费用为1流量无限的边.假设存在序列({p_i}_{i=1}^{2n})使得(b_{p_i}geq b_{p_{i+1}}),那么对每个(i,u'_{p_i})向(u'_{p_{i+1}})连一条费用为0流量无限的边,如果有(b_{p_i}=b_{p_{i+1}}),那么(u'_{p_{i+1}})也要向(u'_{p_i})连一条费用为0流量无限的边,最后(u'_i)向(u_i)一条费用为0流量无限的边.
同样,类似地修改(4).边数就会变成(O(n))条边.
在实现中,可以使用SSPA费用流算法达到(O(fT(|V|,|E|)))的复杂度,其中(f)是总流量,(T(|V|,|E|))是求单源最短路径的复杂度.如果使用Dijkstra算法就可以达到(O(n^2log n))的复杂度.注意到边权必为(0)或(1),因此可以使用01BFS算法达到(O(n^2))的复杂度.
代码(Dijkstra)
代码(01BFS)