当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

6673:Subway

题目描述
一辆地铁,有编号为 $1$ 到 $L$ 的 $L$ 节车厢,这 $L$ 节车厢排成一排,第 $i$ 节车厢在位置 $i$,容量为 $c[i]$ 人,地铁只在第 $1$ 秒至第 $D$ 秒的时间内允许乘客上车 (注:包括第 $1$ 秒和第 $D$ 秒)

所有乘客都要先乘坐手扶电梯到达位置 $p$,每个乘客每秒钟可以向左或者右走动一个单位的距离,上车的时间不计。

现有两组人:

* 第一组有 $n$ 个人,第 $i$ 个人到达位置 $p$ 的时间,为第 $t1[i]$ 秒。
* 第二组有 $m$ 个人,第 $i$ 个人到达位置 $p$ 的时间,为第 $t2[i]$ 秒,他想上第 $y[i]$ 号车厢,如果他走到 $y[i]$ 号车厢时 $y[i]$ 车厢人满了,或者地铁不允许乘客上车,他不会上车。

现在,我们需要给第一组的第 $i$ 个人,决定他打算上的车厢 $x[i]$(如果走到 $x[i]$ 号车厢时,$x[i]$ 号车厢人满了,或者地铁不允许乘客上车,他不会上车),从而最大化第一组人中上车的人数。

地铁里的人形色匆匆,每个人都会以最短的时间,走向自己想要上的车厢所在位置。
输入解释
第一行一个整数 $T$,表示 $T~(1\leq T\leq 20)$ 组数据。
每组数据
* 第一行 5 个整数 $L,p,n,m,D~(1\leq p \leq L \leq 100000, 1 \leq D \leq 100000, 0 \leq n,m \leq 100000)$
* 第二行 $L$ 个整数,第 $i$ 个表示 $c[i]~(0 \leq c[i] \leq 100000)$
* 第三行 $n$ 个整数,表示第一组人下电梯的时间 $(1 \leq t1[i] \leq 100000)$
* 第四行 $m$ 个整数,表示第二组人下电梯的时间 $(1 \leq t2[i] \leq 100000)$
* 第五行 $m$ 个整数,表示第二组人想去的车厢 $(1 \leq y[i] \leq L)$

数据保证,同一时刻,不会有两个人同时到达位置 $p$。
输出解释
每组数据,输出一个整数表示第一组中,最多几个人可以上车。
输入样例
1
3 2 2 1 10
1 1 1
1 3
2
2
输出样例
2
来自杭电HDUOJ的附加信息
Recommend liuyiding

该题目是Virtual Judge题目,来自 杭电HDUOJ

源链接: HDU-6673

最后修改于 2020-10-25T23:33:22+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
6000/4000MS(Java/Others) 32768/32768K(Java/Others)