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;}

A. Another Puzzle from Papyrus（Codeforces 2238）

相关推荐

若依系统 4.7.6 版本定时任务 RCE 漏洞：从 SQL 注入到 JNDI 注入的完整利用链分析

PIC32MZ与DTH-08信号上拉下拉配置实践

报名投票想一站式？这款投票系统报名+投票全流程搞定

更多资讯

没毕业证能考电工证但含金量决定你能不能干这行

建筑电工证考试模拟在哪考？别让实操考试吓退你

焊割工特种作业证图最新政策解读良心建议

枣庄市高压电工证报名在哪考实操考试心里没底怕挂科怎么办

淮安电工证报名网址全国通用吗？外省证书怎么转过来

低压电工证换证材料怎么准备上岗必备全攻略

今日更新

电工证考试及格线你知道多少？值不值得考

南通电工证发证单位考前押题怎么搞？工地太忙根本没时间复习考试

黄陵县高低压电工证怎么考？上岗必备全流程避坑指南

本周精选

安监局电工证分数查询怎么查才能知道含金量高不高

新疆电工作业干活累吗良心建议助你避开考不过的坑

中牟县电工证怎么报名外省证能转吗

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？