logo AlgoBeat OnlineJudge
登录 注册

#215022. [NHSPC 2024] 計程車叫車問題

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

你是某計程車公司老闆,擁有 台計程車。這些計程車都在 軸上,位置分別是 。同時,你接到 名路人的搭車請求,這 名路人也在 軸上,位置分別是 。我們假設上述 個座標均相異。你的任務是為每一位路人指派一台計程車,且每台計程車只能指派給一位路人。你的目標是最小化這 台計程車到其指派路人的距離總和(稱此距離總和為叫車距離總和)。你的程式必須輸出最小叫車距離總和。

舉例來說,如果你有 台計程車(),位置分別在 ),而 名路人位置分別在 ),則最小叫車距離總和為

下圖顯示另一個例子。在這個例子中有台計程車(),位置分別在 ),而 名路人位置分別在 ),則最小叫車距離總和為 (下圖所顯示的計程車指派方式之叫車距離總和即為 )。

:::align{centered} :::

输入格式

  • 代表路人及計程車的數量。
  • 代表第 輛計程車的位置。
  • 代表第 個路人的位置。

输出格式

  • 代表給定輸入的最小叫車距離總和。

样例

样例输入 1

5
3 2 1 5 4
8 6 10 9 7

样例输出 1

25

样例输入 2

5
10 70 30 90 50
71 31 51 91 11

样例输出 2

5

数据范围与提示

測資限制

  • 保證給定的 個座標均相異。

評分說明

本題共有兩組子任務,條件限制如下所示。 每一組可有一或多筆測試資料,該組所有測試資料皆需答對才會獲得該組分數。

子任務 分數 額外輸入限制
1 40
2 60 無額外限制。