Logo Wy Online Judge

WyOJ

题目背景

温馨提示:若您不喜欢本套题目的背景,可以直接去题目描述里看形式化题意。

富樫勇太曾是一名中二病患者,自称“漆黑烈焰使”。如今他已经从中二病毕业,过着平凡的高中生活。然而,他的同班同学小鸟游六花却是一名现役中二病患者,坚信自己拥有“邪王真眼”,并一直寻找着“不可视境界线”。

某天,六花找到了勇太,声称自己通过“邪王真眼”观测到了两个平行世界的力量数值序列 $a$ 和 $b$。她认为,只有当 $a$ 中最弱的力量不低于 $b$ 中最强的力量时,两个世界才能稳定连接,她才能打开“不可视境界线”的大门。

为了帮助六花实现愿望(虽然勇太觉得很羞耻),勇太决定使用“漆黑烈焰使”的力量来调整这些数值。每次操作可以选择任意一个世界中的任意一个数值,使其增加 $1$ 或减少 $1$。由于调整数值会消耗“魔力”,他希望知道最少需要多少次操作,才能让 $a$ 中的最小值大于等于 $b$ 中的最大值。

题目描述

给定两个整数数组 $a$ 和 $b$,长度分别为 $n$ 和 $m$。每次操作可以选择 $a$ 或 $b$ 中的一个元素,将其加 $1$ 或减 $1$。求使得 $\min(a) \ge \max(b)$ 的最小操作次数。

输入格式

第一行包含两个整数 $n, m$,分别表示数组 $a$ 和 $b$ 的长度。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$,表示数组 $a$。

第三行包含 $m$ 个整数 $b_1, b_2, \dots, b_m$,表示数组 $b$。

输出格式

输出一行一个整数,表示最小操作次数。

样例 #1

样例输入 #1

2 2
2 3
3 5

样例输出 #1

3

样例解释 #1

一种最优操作方案为:将 $a_1 = 2$ 增加 $1$ 变为 $3$,将 $b_2 = 5$ 减少 $2$ 变为 $3$。此时 $\min(a)=3$,$\max(b)=3$,满足条件,共操作 $3$ 次。

样例 #2

样例输入 #2

3 2
1 2 3
3 4

样例输出 #2

4

样例解释 #2

将 $a_1$ 增加到 $3$($2$ 次),将 $b_2$ 减少到 $3$($1$ 次),将 $a_2=2$ 增加到 $3$($1$ 次),总共 $4$ 次。

样例 #3

样例输入 #3

3 2
4 5 6
1 2

样例输出 #3

0

样例解释 #3

初始时 $\min(a)=4$,$\max(b)=2$,已经满足条件,不需要操作。

数据范围与提示

本题共 $10$ 个测试点,各测试点规模如下表所示:

测试点编号 $n$ 的范围 $m$ 的范围 元素 $a_i, b_i$ 的范围 特殊性质
$1\sim 3$ $[1,500]$ $[1,500]$ $[1,10000]$ 无
$4\sim 5$ $[1,2000]$ $[1,2000]$ $[1,10^8]$ 无
$6\sim 10$ $[1,10^5]$ $[1,10^5]$ $[1,10^8]$ 无

对于 $100\%$ 的数据,$1 \le n,m \le 10^5$,$1 \le a_i,b_i \le 10^8$。

题目信息
  • 难度 UKE
  • 控制组 group_wxl
  • 时间限制 1 s
  • 空间限制 128 MB
  • 数据大小 1.502 MB
提交统计
  • 提交数 39
  • 通过数 13
  • 通过率 33.3%