统计
  • 建站日期:2021-03-10
  • 文章总数:687 篇
  • 评论总数:723 条
  • 分类总数:10 个
  • 最后更新:12月1日
文章 精密算法

Java 蓝桥杯 国赛 第十一届 C组 试题I:画廊

程序员阿鑫
首页 精密算法 正文


Java蓝桥杯国赛第十一届C组试题I:画廊
-程序员阿鑫-带你一起秃头!
-第1
张图片

#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 ≤ 1001L,R10,1d100,1w100
对于 70 7070% 的评测用例,1 ≤ L , R ≤ 100 , 1 ≤ d ≤ 1000 , 1 ≤ w ≤ 1000 1 ≤ L, R ≤ 100, 1 ≤ d ≤ 1000, 1 ≤ w ≤ 10001L,R100,1d1000,1w1000
对于所有评测用例,1 ≤ L , R ≤ 500 , 1 ≤ d ≤ 100000 , 1 ≤ w ≤ 100000 , 0 ≤ 1 ≤ L, R ≤ 500, 1 ≤ d ≤ 100000, 1 ≤ w ≤ 100000,0 ≤1L,R500,1d100000,1w100000,0 u1 < << u2 < ⋅ ⋅ ⋅ < < · · · <<< uL ≤ d , 0 ≤ ≤ d, 0 ≤d,0 v1 < << v2 < ⋅ ⋅ ⋅ < < · · · <<< vR ≤ d ≤ dd


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:画廊》的全部内容,

感谢您对程序员阿鑫博客的支持!

版权说明
文章采用: 《署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0)》许可协议授权。
版权声明:未标注转载均为本站原创,转载时请以链接形式注明文章出处。如有侵权、不妥之处,请联系站长删除。敬请谅解!

-- 展开阅读全文 --
这篇文章最后更新于2021-1-4,已超过 1 年没有更新,如果文章内容或图片资源失效,请留言反馈,我们会及时处理,谢谢!
Java 蓝桥杯 国赛 第十一届 C组 试题J:答疑
« 上一篇
Java 蓝桥杯 国赛 第十一届 C组 试题H:蓝肽子序列
下一篇 »
为了防止灌水评论,登录后即可评论!
注册登录

HI ! 请登录
注册会员,享受下载全站资源特权。
登陆 注册
社交账号登录

IP地址

热门文章

1
抖音无限礼物模拟小工具分享
2
QQ假红包引流QQ群教程及代码
4
卡QQ永久大会员方法

最新文章

标签