stdKonjac's Blog

 要做到不可替代,就要与众不同。

【货物运输】

题目描述

南沙群岛有N个岛屿上驻扎有解放军边防部队。每个岛屿的位置用一个平面坐标(Xi,Yi)来表示,岛屿间的行程费用被认为是两者间的距离。例如,两个点(X1,Y1),(X2,Y2),它们的直线距离为:《【货物运输】》

军队基地在坐标为(0,0)的岛屿里面,基地存放了常用的生活物资。基地准备给每个岛屿分别送去 Qi(1≤Qi≤1000)单位的货物。唯一负责运输的一艘货轮由基地取出货物,按照岛屿编号的先后顺序运送到每个岛屿(卸货时间忽略不计),然后返回基地。也就是说货物送到第 i-1 个岛屿后,下一个要送去货物的就应该是第 i 个岛屿。可是由于货轮的运载量有限,一次航行最多只能运载C(Q≤C≤10000)单位的货物,所以有可能需要来回基地多次才能将全部货物送完。注意:处于岛屿安全性考虑,货轮可以经过每个岛屿多次,但只能在每个岛屿上一次卸载完货物。最后货轮要回到基地。

请你设计一个运输方案,使得总行程费用最小。

输入格式

第一行为 2 个正整数 N 和 C ,表示岛屿数(不含基地)和货轮的最大运载量。
接下来 N 行,每行三个整数 Xi,Yi 和 Qi,表示按照岛屿的先后顺序,第 i 个岛屿的 X 轴和 Y 轴坐标及其预订货物量。0≤Xi , Yi≤10000 ,每个岛屿(包括基地)的坐标都不同。

输出格式

输出一个实数,表示送完所有货物的最小总行程费用,四舍五入保留 2 位小数。

样例数据 1

输入

3 4
0 3 2
4 0 2
5 0 2

输出

16.00

备注

【样例说明】

《【货物运输】》

从(0,0)出发,装 2 个单位货物到第 1 个岛屿(0,3),然后返回基地;
从(0,0)出发,装 4 个单位货物到第 2 个岛屿(4,0),卸下 2 个单位的货物,接着从第 2 个岛屿到第 3 个岛屿(5,0)并卸下 2 个单位货物;最后从第 3 个岛屿沿直线返回基地。

【数据规模】
对于 30% 的数据:2≤N≤100;
对于 60% 的数据:2≤N≤1000;
对于 100% 的数据:2≤N≤50000;

这道题真是做的我内心崩溃了啊,题解看了半天都还是晕乎乎的!居然是维护单调队列……我啥也不想说了,等以后有机会了再来把思路理清吧,下面是代码:

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*

This site uses Akismet to reduce spam. Learn how your comment data is processed.