本题没有可用的提交语言。

题目描述

您可能注意到，公交车司机有时会经过候车乘客，停在距离乘客与车门最远的位置。虽然具体原因未知（或许并非出于司机的恶意，而是为了让车内乘客更快下车），但某国政府决定在通勤铁路系统中引入自动驾驶功能。该系统需自动控制列车在站台的停靠位置：

1. 问题建模：

   • 站台长度为$0 < L \leq 5000$。
   • 站台上有$0 < M \leq 300$名乘客，其位置为$P_1, P_2, \ldots, P_M$（满足$0 \leq P_1 \leq \ldots \leq P_M \leq L$）。
   • 列车有$0 < N \leq 300$个车门，位置为$D_1, D_2, \ldots, D_N$（满足$0 = D_1 < D_2 < \ldots < D_N \leq L$，$D_1$为基准车门）。
   • 列车停靠位置$S$表示基准车门$D_1$与站台起点的距离。停靠时需保证所有车门均在站台内（即$S + D_N \leq L$）。

2. 目标函数：

   • 乘客$i$到车门$j$的距离为$\text{dist}(i, j, S) = |D_j + S - P_i|$。
   • 需最大化所有乘客到最近车门距离的总和：$\sum_{i=1}^{M} \min_{j=1}^{N} \text{dist}(i, j, S)$。

输入输出

• 输入：
  • 第一行为站台长度$L$、乘客数$M$及乘客位置$P_1, \ldots, P_M$。
  • 第二行为车门数$N$及车门偏移量$D_2, \ldots, D_N$（$D_1$固定为$0$）。
• 输出：
  • 最优停靠位置$S$及对应的距离总和。若有多解，输出任意一个。

示例

输入：

4  
5  
0 1 2 3 4  
4  
1 2 3  

输出：

0.5 2.5  

解释：

• 车门位置：$D=[0, 1, 2, 3]$。
• 当$S=0.5$时：
  • 车门实际位置：$[0.5, 1.5, 2.5, 3.5]$。
  • 乘客$0$最近车门$0.5$，距离$0.5$；乘客$1$最近车门$1.5$，距离$0.5$；依此类推。
  • 总距离：$0.5 + 0.5 + 0.5 + 0.5 + 0.5 = 2.5$。

来源

Northeastern Europe 2002, Northern Subregion