#I 画廊
时间限制: 1.0s 内存限制: 512.0MB 本题总分：25 分
问题描述
小蓝办了一个画展，在一个画廊左右两边陈列了他自己的作品。为了使画展更有意思，小蓝没有等距陈列自己的作品，而是按照更有艺术感的方式陈列。
在画廊的左边陈列了 L LL 幅作品，在画廊的右边陈列了 R RR 幅作品，左边的作品距离画廊的起点依次为 u1, u2, · · · , uL，右边的作品距离画廊起点依次为 v1, v2, · · · , vR。
每周，小蓝要整理一遍自己的每一幅作品。整理一幅作品的时间是固定的，但是要带着沉重的工具。从一幅作品到另一幅作品之间的距离为直线段的长度。
小蓝从画廊的起点的正中央（左右两边的中点）出发，整理好每一幅画，最终到达画廊的终点的正中央。已知画廊的宽为 w ww。
请问小蓝最少带着工具走多长的距离？
输入格式
输入的第一行包含四个整数 L , R , d , w L, R, d, wL,R,d,w，表示画廊左边和右边的作品数量，
以及画廊的长度和宽度。
第二行包含 L LL 个正整数 u1, u2, · · · , uL，表示画廊左边的作品的位置。
第三行包含 R RR 个正整数 v1, v2, · · · , vR，表示画廊右边的作品的位置。
输出格式
输出一个实数，四舍五入保留两位小数，表示小蓝最少带着工具走的距离。
测试样例1
Input：
3 3 10 2
1 3 8
2 4 6
Output：
14.71
Explanation：
小蓝从起点开始，首先到达左边第一幅作品（走动距离 √2），然后到达左
边第二幅作品（走动距离 2），然后到达右边第一幅作品（走动距离 √5），然后
到达右边第二幅和第三幅作品（走动距离 2 和 2），然后到达左边第三幅作品（走动距离 2√2），最后到达画廊终点（走动距离 √5）。
总共距离为 √2 + 2 + √5 + 2 + 2 + 2 √2 + √5 ≈ 14.71。评测用例规模与约定
对于 40 4040% 的评测用例，1 ≤ L , R ≤ 10 , 1 ≤ d ≤ 100 , 1 ≤ w ≤ 100 1 ≤ L, R ≤ 10, 1 ≤ d ≤ 100, 1 ≤ w ≤ 1001≤L,R≤10,1≤d≤100,1≤w≤100。
对于 70 7070% 的评测用例，1 ≤ L , R ≤ 100 , 1 ≤ d ≤ 1000 , 1 ≤ w ≤ 1000 1 ≤ L, R ≤ 100, 1 ≤ d ≤ 1000, 1 ≤ w ≤ 10001≤L,R≤100,1≤d≤1000,1≤w≤1000。
对于所有评测用例，1 ≤ L , R ≤ 500 , 1 ≤ d ≤ 100000 , 1 ≤ w ≤ 100000 , 0 ≤ 1 ≤ L, R ≤ 500, 1 ≤ d ≤ 100000, 1 ≤ w ≤ 100000,0 ≤1≤L,R≤500,1≤d≤100000,1≤w≤100000,0≤ u1 < << u2 < ⋅ ⋅ ⋅ < < · · · <<⋅⋅⋅< uL ≤ d , 0 ≤ ≤ d, 0 ≤≤d,0≤ v1 < << v2 < ⋅ ⋅ ⋅ < < · · · <<⋅⋅⋅< vR ≤ d ≤ d≤d。
code：
import java.io.IOException;
import java.io.BufferedReader;
import java.io.StreamTokenizer;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
public static void main(String[] args) throws IOException {
StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
int L, R, d, w;
in.nextToken();
L = (int)in.nval;
in.nextToken();
R = (int)in.nval;
in.nextToken();
d = (int)in.nval;
in.nextToken();
w = (int)in.nval;
int[] left = new int[L + 1];
int[] right = new int[R + 1];
for (int i = 1; i <= L; i++) {
in.nextToken();
left[i] = (int)in.nval;
}
for (int i = 1; i <= R; i++) {
in.nextToken();
right[i] = (int)in.nval;
}
double ww = w * w;
double[][][] visit = new double[2][L + 1][R + 1];
double mm = w * w / 4.0, res = Double.POSITIVE_INFINITY;
double llast = Math.sqrt((d - left[L]) * (d - left[L]) + mm),
rlast = Math.sqrt((d - right[R]) * (d - right[R]) + mm);
Step now, next;
Queue<Step> queue = new LinkedList();
queue.offer(new Step(visit[0][1][0] = Math.sqrt(mm + left[1] * left[1]), 1, 0, true));
queue.offer(new Step(visit[1][0][1] = Math.sqrt(mm + right[1] * right[1]), 0, 1, false));
while (queue.size() > 0) {
now = queue.poll();
if (now.l == L && now.r == R) {
now.len += now.here ? llast : rlast;
if (now.len < res) res = now.len;
continue;
}
if (now.l < L) {
if (now.here) next = new Step(now.len + Math.sqrt((left[now.l + 1] - left[now.l]) * (left[now.l + 1] - left[now.l])), now.l + 1, now.r, true);
else next = new Step(now.len + Math.sqrt(ww + (left[now.l + 1] - right[now.r]) * (left[now.l + 1] - right[now.r])), now.l + 1, now.r, true);
if (visit[0][next.l][next.r] == 0 || visit[0][next.l][next.r] > now.len) {
visit[0][next.l][next.r] = now.len;
queue.offer(next);
}
}
if (now.r < R) {
if (now.here) next = new Step(now.len + Math.sqrt(ww + (right[now.r + 1] - left[now.l]) * (right[now.r + 1] - left[now.l])), now.l, now.r + 1, false);
else next = new Step(now.len + Math.sqrt((right[now.r + 1] - right[now.r]) * (right[now.r + 1] - right[now.r])), now.l, now.r + 1, false);
if (visit[1][next.l][next.r] == 0 || visit[1][next.l][next.r] > now.len) {
visit[1][next.l][next.r] = now.len;
queue.offer(next);
}
}
}
System.out.printf("%.2fn", res);
}
static class Step {
int l, r;
boolean here;
double len;
Step(double len, int l, int r, boolean here) {
this.l = l;
this.r = r;
this.len = len;
this.here = here;
}
}
}应该是道特殊的最小树生成
但比赛的时候广搜写一半才发现的
自信不会超时就没改
以上是《Java 蓝桥杯 国赛 第十一届 C组 试题I：画廊》的全部内容，
感谢您对程序员阿鑫博客的支持！
版权声明：未标注转载均为本站原创，转载时请以链接形式注明文章出处。如有侵权、不妥之处，请联系站长删除。敬请谅解！
