#PQJ476x6139. QOJ 476_6139

    ID: 2992 传统题 1000ms 512MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:NOI 2021 统一省选贪心枚举

QOJ 476_6139

全国青少年信息学奥林匹克竞赛 Day1(A 卷)卡牌游戏(card) 卡牌游戏(card) 【题目描述】 Alice 有n 张卡牌,第i(1 ≤i ≤n)张卡牌的正面有数字ai,背面有数字bi,初 始时所有卡牌正面朝上。 现在Alice 可以将不超过m 张卡牌翻面,即由正面朝上改为背面朝上。Alice 的目 标是让最终朝上的n 个数字的极差(最大值与最小值的差)尽量小。请你帮Alice 算一 算极差的最小值是多少。 【输入格式】 从文件card.in 中读入数据。 第一行两个正整数n, m,代表卡牌张数与至多翻面张数。 第二行n 个正整数,第i 个数字表示ai。 第三行n 个正整数,第i 个数字表示bi。 数据保证卡牌上的2n 个数字互不相同,且卡牌按照ai 升序给出。 【输出格式】 输出到文件card.out 中。 仅一行一个整数表示答案。 【样例1 输入】 1 6 3 2 8 11 13 14 16 19 3 10 18 2 3 6 7 【样例1 输出】 1 8 【样例1 解释】 最优方案之一:将第1, 5, 6 张卡牌翻面,最终朝上的数字依次为10, 11, 13, 14, 6, 7, 极差为14 −6 = 8。 第2 页 共7 页

全国青少年信息学奥林匹克竞赛 Day1(A 卷)卡牌游戏(card) 【样例2】 见选手目录下的card/card2.in 与card/card2.ans。 【样例3】 见选手目录下的card/card3.in 与card/card3.ans。 【数据范围】 对于所有测试数据:3 ≤n ≤106,1 ≤m < n,1 ≤ai, bi ≤109。 每个测试点的具体限制见下表: 测试点编号 n ≤ 特殊限制 1 ∼2 10 无 3 ∼4 500 5 ∼6 5 × 105 m ≤1000 7 1 × 105 无 8 4 × 105 9 7 × 105 10 1 × 106 第3 页 共7 页