蓝桥杯2026年第十七届省赛真题-回收处理

在自动化工厂的流水线上，依次排列着 3N 个部件。每个部件都标有一个价格 ai：若执行回收，该标价即为收益；若执行处理，该标价则计为成本。

作为厂区负责人，小蓝的任务是从这 3N 个部件中挑选出两批特定组别：

1. 回收组：挑选出恰好 N 个部件进行回收，总收益记为 R。

2. 处理组：挑选出恰好 N 个部件进行处理，总成本记为 C。

由于流水线是不可逆的单向传送，挑选过程必须遵守严格的先后顺序：任何一个被回收的部件，其原始位置都必须早于所有被处理的部件（即若把回收部件的下标记为 p1 < p2 < · · · < pN，处理部件的下标记为 q1 < q2 < · · · < qN，则必须满足 pN < q1）。

在满足上述顺序的前提下，流水线上剩下的 N 个部件将被直接弃置，不产生任何收益或成本。

现在，小蓝希望通过合理的方案，使得回收的总收益减去处理的总成本（R − C）尽可能大。对此，请你计算出这个差值的最大可能结果。

第一行包含一个整数 N，表示每组选取的部件数量。

第二行包含 3N 个整数 a1, a2, . . . , a3N，表示流水线上从左到右每个部件的标价。

给定的网络可能包含重边或自环。

输出一个整数，表示在满足所有约束的前提下，R − C 的最大可能值。

【样例说明】

最优的方案为：回收第 2、3 个部件，处理第 4、6 个部件，此时 R =10 + 5 = 15，C = 1 + 1 = 2，R − C = 13。

【评测用例规模与约定】

对于 40% 的评测用例，1 ≤ N ≤ 1000。对于所有评测用例，1 ≤ N ≤ 10⁵，1 ≤ ai ≤ 10⁹。