A. Another Puzzle from Papyrus（Codeforces 2238）

A. Another Puzzle from Papyrus题意简述给定两个长度为n的数组a和b。可以执行两种操作选择一个位置i把a_i减少1代价为1任意重排整个数组a代价为c。要求把a变成b求最小总代价如果无法做到输出-1。核心观察1. 减法总次数是固定的如果某个方案可行最终数组和一定从sum(a)变为sum(b)。每次减法只会让总和减少1所以无论中间怎么重排减法次数一定是sum(a) - sum(b)如果sum(a) sum(b)因为不能增加数字直接无解。2. 重排最多只需要做一次重排不会改变数值只会改变元素顺序。如果决定使用重排那么可以一开始就把元素调整到最合适的位置然后再做减法。多次重排只会多花c不会减少减法总次数所以只需要考虑两种情况方案 1不重排 方案 2重排一次情况一不重排不重排时第i个元素只能变成第i个目标值。因此必须满足a_i b_i 对所有 i 成立如果成立代价就是sum(a) - sum(b)示意a: 4 5 2 3 | | | | b: 3 5 1 2 每一列都要求上面的数 下面的数。情况二重排一次重排后本质上是在问能不能把a中的每个数分配给b中的一个数使得被分配的a不小于对应的b最简单可靠的判断方法是把两个数组都排序然后小的配小的。sort(a): a_1 a_2 ... a_n sort(b): b_1 b_2 ... b_n如果对所有位置都有sort(a)[i] sort(b)[i]则重排后可行。为什么小配小是对的目标 b 越小越容易被满足。 如果最小的 a 连最小的 b 都满足不了 那它也不可能满足更大的 b。所以排序后一一比较就能判断是否存在一种合法匹配。如果可行代价为c sum(a) - sum(b)其中c是一次重排代价后面是固定的减法次数。算法流程对每组测试数据读入n, c, a, b如果sum(a) sum(b)输出-1计算固定减法代价decCost sum(a) - sum(b)检查不重排是否可行若可行用decCost更新答案排序a和b检查重排一次是否可行若可行用c decCost更新答案如果两个方案都不可行输出-1否则输出最小答案。图表示意策略判断条件代价不重排每个位置a_i b_isum(a) - sum(b)重排一次排序后每个位置sort(a)[i] sort(b)[i]c sum(a) - sum(b)以样例第一组为例a [5, 2, 3] b [2, 3, 4] 不重排 位置 2: 2 3不可行 重排 sort(a) [2, 3, 5] sort(b) [2, 3, 4] 每个位置都满足 代价 c (sum(a) - sum(b)) 5 (10 - 9) 6易错点不要只判断sum(a) sum(b)。总和够不代表一定可行例如小元素可能无法匹配较大的目标。重排代价最多加一次。多次重排没有任何收益。判断重排可行时要把a和b都排序而不是只排序一个数组。即使重排可行也要和“不重排”的答案取最小值因为不重排可能更便宜。复杂度分析每组测试数据排序一次时间复杂度O(n log n) 空间复杂度O(n)本题n 100复杂度非常充足。C 代码实现#includebits/stdc.husingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intT;cinT;while(T--){intn;longlongc;cinnc;vectorinta(n),b(n);longlongsumA0,sumB0;for(inti0;in;i){cina[i];sumAa[i];}for(inti0;in;i){cinb[i];sumBb[i];}constlonglongINF(1LL60);longlongansINF;// 如果总和都不够减法无法让 a 变大直接无解。if(sumAsumB){cout-1\n;continue;}// 任意可行方案中减法次数都是固定的。longlongdecCostsumA-sumB;// 方案 1不重排。// 每个位置必须能从 a[i] 减到 b[i]。boolokSameOrdertrue;for(inti0;in;i){if(a[i]b[i]){okSameOrderfalse;break;}}if(okSameOrder){ansmin(ans,decCost);}// 方案 2重排一次。// 排序后小配小如果每一对都满足 sa[i] sb[i]就存在合法匹配。vectorintsaa,sbb;sort(sa.begin(),sa.end());sort(sb.begin(),sb.end());boolokAfterReordertrue;for(inti0;in;i){if(sa[i]sb[i]){okAfterReorderfalse;break;}}if(okAfterReorder){ansmin(ans,cdecCost);}cout(ansINF?-1:ans)\n;}return0;}