将 看作是一段区间，那么考虑每次交换操作的贡献： 可以发现两区间无交集无论如何交换都满足其贡献 （事实上，如果令 ，那么 ），而有交集则 ，所以一定是尽量地选择有无集的区间交换。 引理： 时，「操作刚好 次」和「操作不超过 次」是等价的。 证明：将「操作不超过 次」的最优解执行完后，因为
展开全文
G题：题目大意对于数组大小为n的两个数组a，b在a上操作k次交换使得 最大。看到这题想到的是如果我能定量的知道每次交换带来的收益就好了，如果每次交换的收益都是最优的那么结果也是最优的这就是经典的贪心算法，下面对交换的贡献进行讨论：对于（a1，b1）（a2，b2）由于绝对值的存在无论a1，b1大小其值
展开全文
题意：给与两个长度为n的a,b数组，你可以交换a数组中两个元素位置，你恰好进行k次操作后 的最大值？ 思路：首先我们思考一下什么样的两个数交换后的结果会大：假如有两对数:（a1,b1），（a2,b2）原结果为abs(a1-b1)+abs(a2-b2)如果a1>b1&&a2>
展开全文
题目描述 Given two arrays , with length , you should perform exactly operations in array . For each operation, choose elements , () and swap the pos
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
