企业官网建设流程全解析

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是一次重排代价，后面是固定的减法次数。

算法流程

对每组测试数据：

1. 读入n, c, a, b；
2. 如果sum(a) < sum(b)，输出-1；
3. 计算固定减法代价decCost = sum(a) - sum(b)；
4. 检查不重排是否可行，若可行，用decCost更新答案；
5. 排序a和b，检查重排一次是否可行，若可行，用c + decCost更新答案；
6. 如果两个方案都不可行，输出-1，否则输出最小答案。

图表示意

以样例第一组为例：

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

易错点

1. 不要只判断sum(a) >= sum(b)。总和够不代表一定可行，例如小元素可能无法匹配较大的目标。
2. 重排代价最多加一次。多次重排没有任何收益。
3. 判断重排可行时要把a和b都排序，而不是只排序一个数组。
4. 即使重排可行，也要和“不重排”的答案取最小值，因为不重排可能更便宜。

复杂度分析

每组测试数据排序一次：

时间复杂度：O(n log n) 空间复杂度：O(n)

本题n <= 100，复杂度非常充足。

C++ 代码实现

#include<bits/stdc++.h>usingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intT;cin>>T;while(T--){intn;longlongc;cin>>n>>c;vector<int>a(n),b(n);longlongsumA=0,sumB=0;for(inti=0;i<n;++i){cin>>a[i];sumA+=a[i];}for(inti=0;i<n;++i){cin>>b[i];sumB+=b[i];}constlonglongINF=(1LL<<60);longlongans=INF;// 如果总和都不够，减法无法让 a 变大，直接无解。if(sumA<sumB){cout<<-1<<'\n';continue;}// 任意可行方案中，减法次数都是固定的。longlongdecCost=sumA-sumB;// 方案 1：不重排。// 每个位置必须能从 a[i] 减到 b[i]。boolokSameOrder=true;for(inti=0;i<n;++i){if(a[i]<b[i]){okSameOrder=false;break;}}if(okSameOrder){ans=min(ans,decCost);}// 方案 2：重排一次。// 排序后小配小，如果每一对都满足 sa[i] >= sb[i]，就存在合法匹配。vector<int>sa=a,sb=b;sort(sa.begin(),sa.end());sort(sb.begin(),sb.end());boolokAfterReorder=true;for(inti=0;i<n;++i){if(sa[i]<sb[i]){okAfterReorder=false;break;}}if(okAfterReorder){ans=min(ans,c+decCost);}cout<<(ans==INF?-1:ans)<<'\n';}return0;}