题面有误
查看原帖
题面有误
595948
Sky_Maths楼主2023/11/7 13:58

修改后题面如下

某长途巴士发车时刻为 00,到达终点的时刻为 XX。车上装有饮水机,乘客和司机可以在车上装水喝。出发前水箱是空的,饮水机的容量可以视为无限大。
途中有 NN 个服务站,依次编号为 1…N1\ldots N。巴士到达服务站 i(1≤i≤N)i(1\le i\le N) 的时间是 SiS_i。保证 S1,S2,…,SNS_1,S_2,\ldots,S_N 严格递增。
在服务站或出发前可以给饮水机加水,水价为每升 WW 円。

本次巴士有 MM 名乘客(不含司机),乘客 j(1≤j≤M)j(1\le j\le M) 在时刻 kT+Dj(k=0,1,2,…)kT+D_j(k=0,1,2,\ldots) 需要装 11 升水,在其他时刻不装水。保证 1≤Dj<T1≤ D_j < T。
司机在时刻 kT(k=0,1,2,…)kT(k=0,1,2,\ldots) 需要装 11 升水,在其他时刻不装水,注意,在出发时司机会从车上装 11 升水。如果某一名乘客想装水时饮水机没水了,这名乘客会怒而下车,此时需要向这名乘客退 CjC_j 円。特别的,你需要保证司机必须有水装。

保证不会出现两人在同一时刻需要装水的情况。保证在服务站或是到达终点时没有人要装水。

试求最小花销(买水的总费用 ++ 所有退的车费)是多少。

**题目译自 [JOISC 2017](https://www.ioi-jp.org/camp/2017/2017-sp-tasks/index.html) Day3 T1「[長距離バス](https://www.ioi-jp.org/camp/2017/2017-sp-tasks/2017-sp-d3.pdf)([Long Distance Coach](https://www.ioi-jp.org/camp/2017/2017-sp-tasks/2017-sp-d3-en.pdf))」**

某长途巴士发车时刻为 $0$,到达终点的时刻为 $X$。车上装有饮水机,乘客和司机可以在车上装水喝。出发前水箱是空的,饮水机的容量可以视为无限大。  
途中有 $N$ 个服务站,依次编号为 $1\ldots N$。巴士到达服务站 $i(1\le i\le N)$ 的时间是 $S_i$。保证 $S_1,S_2,\ldots,S_N$ 严格递增。  
在服务站或出发前可以给饮水机加水,水价为每升 $W$ 円。  

本次巴士有 $M$ 名乘客(不含司机),乘客 $j(1\le j\le M)$ 在时刻 $kT+D_j(k=0,1,2,\ldots)$ 需要装 $1$ 升水,在其他时刻不装水。保证 $1≤ D_j < T$。  
司机在时刻 $kT(k=0,1,2,\ldots)$ 需要装 $1$ 升水,在其他时刻不装水,注意,在出发时司机会从车上装 $1$ 升水。如果某一名乘客想装水时饮水机没水了,这名乘客会怒而下车,此时需要向这名乘客退 $C_j$ 円。特别的,你需要保证司机必须有水装。

**保证不会出现两人在同一时刻需要装水的情况。保证在服务站或是到达终点时没有人要装水。**

试求最小花销(买水的总费用 $+$ 所有退的车费)是多少。
2023/11/7 13:58
加载中...