【转载】思考题：二位偏序上的最优化调整法

userId_undefined
FanBoys

2026-08-03 10:09:51

发布于：安徽

10阅读
0回复
0点赞

排序贪心是贪心的经典形式。具体来说，如果能证明某些逆序对总能被调整成更优的形式（例如邻项交换或者把最值换到开头结尾），我们就可以立刻得到最优解中不存在这种逆序对，于是最优解可以排序后考虑。

更一般的最优性调整法，其实也可以被看成一种“逆序对”调整：一个调整规则 Δ\Delta 通常可以表述为：一个解（或者最优解）中（满足某种条件）的局部 xx 调整成局部 yy 一定会变得更优。这可以视为一种局部之间的偏序 x⪯yx\preceq y，且最优解只需要在 ⪯\preceq 的极值上考虑。然而，一般的偏序的极值性质并不好，有没有什么偏序的极值是好的呢？

二维偏序满足这一点，二维偏序的极值是垂直方向上的一个单调序列/折线。（或者说，极值一定是反链，而二维偏序的反链是互补的二维偏序上的链，即上升子序列，或者说画到平面上是折线。）

因此，不仅排序贪心（一维的全序或者接近全序）可以做，基于二维偏序（比如区间、或者两个值）的调整也都可以做，即可以用平面上的折线刻画最优解的形式。请你完成以下问题：

问题1. 有 nn 种商品，在 X,YX,Y 两家商店出售，第 ii 种商品在两家商店的价格分别是 xi,yix_i,y_i。价格都是 ≤109\leq10^9 的正整数。现在每家商店各自推出了买一赠一活动，买一件商品可以任选赠送至多一件同商店的商品。

你要获取每种商品恰好各一件，并且来自两家商店的商品数量相等，最小化总花费。保证 nn 是偶数。

n≤105n\leq10^5

问题2.1. 有 nn 种商品，在 X,YX,Y 两家商店出售，第 ii 种商品在两家商店的价格分别是 xi,yix_i,y_i。价格都是 ≤109\leq10^9 的正整数。现在你要在两家商店分别购买 cx,cyc_x,c_y 个物品且购买的物品不能重复，最小化总花费。

n≤105n\leq10^5

问题2.2. [AGC018C] 有 nn 种商品在 X,Y,ZX,Y,Z 三家商店出售，第 ii 种商品在三家商店的价格分别是 xi,yi,zix_i,y_i,z_i。现在你要分别在三家商店购买 cx,cy,czc_x,c_y,c_z 种商品且 cx+cy+cz=nc_x+c_y+c_z=n。购买的物品不能重复，最大化总花费。

n≤105n\leq10^5

问题2.3. [AGC018C加强版] 考虑有四家店（或者说四种颜色）的情况，你有哪些做法？

n≤105n\leq10^5

问题3.1. [qoj9222弱化版] 有 nn 种商品，在 X,YX,Y 两家商店出售，第 ii 种商品在两家商店的价格分别是 xi,yix_i,y_i。价格都是 ≤109\leq10^9 的正整数。现在每家商店各自推出了买一赠一活动，买一件商品可以任选赠送至多一件同商店价格相等或更低的商品。

你要获取每种商品各一件，最小化总花费。

n≤5000n\leq5000（原题 n≤105n\leq10^5）

问题3.2. 有 nn 种商品和常数 kk，在 X,YX,Y 两家商店出售，第 ii 种商品在两家商店的价格分别是 xi,yix_i,y_i。价格都是 ≤109\leq10^9 的正整数。现在每家商店各自推出了赠品活动，每买一件商品之后可以任选赠送至多 kk 件同商店价格相等或更低的商品。

你要获取每种商品各一件，最小化总花费。

n≤1000,k≤10n\leq1000,k\leq10

问题4. [P9521 JOISC2022 D1T2]

有一个 HH 行 WW 列的网格。第 ii 行第 jj 列记作 (i,j)(i,j)。网格里四个方向的相邻格子可以走。第 ii 行相邻格之间行走需要 AiA_i 秒。第 jj 列相邻格之间行走需要 BjB_j 秒。

现在要从 (1,1)(1,1) 走到 (H,W)(H,W)，并且只能向行、列编号增大的方向走，请你求出最短路径。

答案

问题1

设 k=n4k=\dfrac{n}{4} 只需要在两个商店中各买 kk 个物品即可

能否把两个商店中买的物品分开？

对于两个物品 x1,y1,x2,y2x_1,y_1,x_2,y_2，采用邻项交换的方式，比较 x1+y2x_1+y_2 和 x2+y1x_2+y_1 的大小，即比较 x1−y1x_1-y_1 和 x2−y2x_2-y_2，因而按照 x−yx-y 排序，前一段在 XX 店买，后一段在 YY 店买，用堆扫一遍，预处理前缀后缀，枚举分界线，分别找 kk 个最小价格的即可

问题2.1

没有赠送，但是告诉每个商店买多少物品，改变堆的大小即可

问题2.2

在前面按照 x−yx-y 的降序排序基础上，枚举一个分界线，在前一部分中买 cxc_x 个 XX 店中的物品和 ww 个 ZZ 店里的物品，在后一部分买 cyc_y 个 YY 店中的物品和 cz−wc_z-w 个 ZZ 个物品

问题转化为如何选择 XX 店里的东西和 ZZ 店里的东西，和上面一样，前半部分再按照 x−zx-z 排序，然后用堆从前往后扫一遍维护即可

问题2.3

又多了一位，可以利用 WQS\text WQS 二分降维处理

老规矩，按照 x−yx-y 排序，枚举分界线，之后有一个 cz+cwc_z+c_w 的二维情况，怎么维护？

一开始先把 ZZ 和 WW 两店中的物品当成能够从任何一个买，先把二者合并为一个大的限制

现在，假设在 ZZ 商店中买了 cz′c_z' 个物品，WW 商店中买了 cw′c_w' 个物品，判断 czc_z 和 cz′c_z'，cwc_w 和 cw′c_w' 的大小

如果 cz=cz′c_z=c_z'，那么恰好；如果 cz′>czc_z'>c_z，买多了，那么考虑把 ZZ 商店中所有东西涨价，让 cz′c_z' 变小；如果 cz′c_z' 因为加价加太多，需要跌价，使得 cz′c_z' 又变大，直到恰好 cz=cz′c_z=c_z'。如果 cz′<czc_z'<c_z 或者考虑 cwc_w 也是同理

前提是与之有关的函数必须是下凸的，记选了 cz′c_z' 个 ZZ 店里的物品，代价为 f(cz′)f(c_z') 越小越好，保证 f′(cz′)f'(c_z') 单调递增或者 f′′(cz′)f''(c_z') 恒为正

因而，全选 ZZ 或者全不选 ZZ 店里的东西应当为代价非常大，因而需要它是一个下凸包，给下凸包加上一个 g(cz′)=kcz′(k≠0)g(c_z')=kc_z'(k\neq0) 的正比例函数，需要让凸包的一条边变平。改变 kk 个大小，可以让任意一条线段变平，任意一个 cz′c_z' 都可以通过调控对应到代价的最小值。

因而，通过上面的证明，直到可以通过这样的微调而得到最终的 cz′=czc_z'=c_z，二分加的价格 pp，得到最终的结果即可。这就是 WQS\text WQS 二分

问题3.1

当 k=1k=1 的时候的特例情况，同问题3.2，此处略

问题3.2

先考虑一个边界情况：假如我们已经确定好每个商品在哪个商店买，在 XX 店里买的是 x1∼xnx_1\sim x_n，在 YY 店里买的是 y1∼yny_1\sim y_n，按照降序排序，把最贵的买了，把接下来 kk 个当赠品拿来。这样一定是最划算的

怎么确定商品在哪个商店买？不能按照前面的方式排序，因为有可能有商品是送的，无法直接计算它们的贡献

当 x1>x2,y1<y2x_1>x_2,y_1<y_2 的时候，显然去 XX 商店买 22 号商品，去 YY 商店买 11 号商品，即便是送的也无妨

放到平面直角坐标系上，这个时候 (x2,y2)(x_2,y_2) 在 (x1,y1)(x_1,y_1) 的左上方，形成一个类似逆序对的情况，虽然不能够用简单的线段划开，但可以用一条单调的折线把它们分开，这条折线右下角一定去 YY 商店买，左上角一定去 XX 商店买

由于偏序关系一定是满足这样的情况，因而这条直线一定是单调递增的，且一定能够完美分隔

对于所有这样能够分开两部分商品的折线 LL 取最小值，由于是整点，可以考虑对这条单调的折线进行 DP\tt DP，使得两部分的代价最小

为了 DP\tt DP 的简便，可以进行规定：

  1. {xi}{yi}\{x_i\}\{y_i\} 都是整数排列，可以通过离散化进行实现，不影响 DP\tt DP，到时候可以还原
  2. 对折线进行 DP\tt DP，每次往右或往上走一格，下面分给 YY，上面分给 XX。
  3. 具体的转移式：设 dp[i][j][a][b]dp[i][j][a][b] 表示向上走了 ii 步，向右走了 jj 步，到达 (i,j)(i,j) 位置，有 aa 个元素归到 XX 店，bb 个元素归到 YY 店。此处以折线往上走为例，一个点可能会被处理到 YY 买，转移 dp[i+1][j][a][b+1]=dp[i][j][a][b]+ypdp[i+1][j][a][b+1]=dp[i][j][a][b]+y_p
  4. 后续的优化：可以只存一个，因为离散化之后，a+b=i+ja+b=i+j，以及其他的 DP\tt DP 优化

问题4

通过每行每列都有一个通行代价，行依次为 A1∼AHA_1\sim A_H，列依次为 B1∼BWB_1\sim B_W，从 (1,1)(1,1) 走到 (H,W)(H,W) 的最小代价是多少？

假设在 B1,B2,A1,A2B_1,B_2,A_1,A_2 对应的边 X1,X2,Y1,Y2X_1,X_2,Y_1,Y_2 构成的网格，先往右后往上的代价为：B1(Y2−Y1)+A2(X2−X1)B_1(Y_2-Y_1)+A_2(X_2-X_1)，先往上后往右的代价为 B2(Y2−Y1)+A1(X2−X1)B_2(Y_2-Y_1)+A_1(X_2-X_1)，即比较 (B2−B1)(Y2−Y1)(B_2-B_1)(Y_2-Y_1) 和 (A2−A1)(X2−X1)(A_2-A_1)(X_2-X_1)，由于 AA 对应 YY，BB 对应 XX，因而移项，比较 A2−A1Y2−Y1\dfrac{A_2-A_1}{Y_2-Y_1} 和 B2−B1X2−X1\dfrac{B_2-B_1}{X_2-X_1}

代价除以间隔，有点类似在新的平面直角坐标系下的斜率定义，即比较斜率，把原来的矩形的横纵坐标分开考虑，最终走斜率较小的边

在矩形内部，考虑三条边权值为 A1,A2,A3A_1,A_2,A_3，对应边为 Y1,Y2,Y3Y_1,Y_2,Y_3，同理比较 A2−A1Y2−Y1\dfrac{A_2-A_1}{Y_2-Y_1} 和 A3−A2Y3−Y2\dfrac{A_3-A_2}{Y_3-Y_2}，若满足后者大于等于前者，则类似于产生逆序对，不能插入任何不走 A2A_2，只走对应较小的那条边，最终保留 (Y,A)(Y,A) 形式的凸包，沿着斜率较小的边走，即可求出答案。同理可以求出 (X,B)(X,B) 形式凸包。

总结

因而，当我们的限制是一个二位偏序的时候，也可以通过一条折线来进行描述，从而进行划分，完成贪心。

最后，买东西请不要到OI商店中购买！！！！！

userId_undefined
去预览
0/2000

全部评论 1

  • userId_undefined
    FanBoys

    看懂的可以试试AT_agc018_c，和思考题一样

    2026-08-03 来自 安徽

    0

热门讨论