Codeforces 967 C 题解报告

一、题目

http://codeforces.com/contest/967/problem/C

二、思路

(一)如果是同一楼层,则直接走过去,不用爬楼梯也不用乘电梯。 (二)如果是不同楼层,分别计算爬楼梯和乘电梯所用的时间,取最小值。 (1)在计算爬楼梯所用时间时,若起始房间旁边只有一个楼梯,计算从起始房间经过该楼梯到达终点房间所需的时间。 若起始房间旁边有两个或更多的楼梯,要分别计算从离起始房间号最近的左右两边的两个楼梯爬上去到达终点房间所需的时间,再取最小值。 (2)乘电梯的道理与爬楼梯的道理一样。 (3)从(1)和(2)的结果中,取最小值。

三、代码

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int main()
{
    int n, m, c1, c2, v; //层数,每层section数,楼梯数,电梯数,电梯每单位时间能升降的层数
    scanf("%d %d %d %d %d", &n, &m, &c1, &c2, &v);
    int a[c1], b[c2];
    for(int i = 0; i < c1; i++)
    {
        scanf("%d", &a[i]);
    }
    for(int i = 0; i < c2; i++)
    {
        scanf("%d", &b[i]);
    }
    int q, floor1, room1, floor2, room2; //查询几次,起始房间的层号和房间号,目标房间的层号和房间号
    int updownPos; //楼梯或电梯的位置
    scanf("%d", &q);
    while(q--)
    {
        int ans=1000000000, k; //k表示第几个楼梯或电梯
        scanf("%d %d %d %d", &floor1, &room1, &floor2, &room2);
        if(floor1 == floor2)
        {
            printf("%d\n", abs(room2 - room1));
            continue;
        }
        //爬楼梯,用二分查找法选择爬第几个楼梯
        k = lower_bound(a, a + c1, room1) - a;  
        if(k < c1)
        {
            updownPos = a[k];
            ans = min(ans, abs(updownPos - room1) + abs(floor2 - floor1) + abs(room2 - updownPos));
        }
        if(k > 0)
        {
            updownPos = a[k-1];
            ans = min(ans, abs(updownPos - room1) + abs(floor2 - floor1) + abs(room2 - updownPos));
        }
        //乘电梯,用二分查找法选择乘哪个电梯
        k = lower_bound(b, b + c2, room1) - b;
        if(k < c2)
        {
            updownPos = b[k];
            ans = min(ans, abs(updownPos - room1) + (abs(floor2 - floor1) + v - 1) / v + abs(room2 - updownPos));
        }
        if(k > 0)
        {
            updownPos = b[k - 1];
            ans = min(ans, abs(updownPos - room1) + (abs(floor2 - floor1) + v - 1) / v + abs(room2 - updownPos));
        }
        printf("%d\n", ans);
    }
    return 0;
}

原文发布于微信公众号 - 海天一树(gh_de7b45c40e8b)

原文发表时间:2018-04-30

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏AI科技大本营的专栏

谷歌大脑深度学习从入门到精通视频课程[6.3]:自动编码器——例子说明

AI100 已经引入 Hugo Larochelle 教授的深度学习课程,会在公众号中推送,并且对视频中的 PPT 进行讲解。课后,我们会设计一系列的问题来巩...

35030
来自专栏绿巨人专栏

读书笔记: 博弈论导论 - 02 - 引入不确定性和时间

32160
来自专栏AI研习社

机器人参加高考数学22分钟拿105分,究竟怎么做到的?

AI 研习社按:2017 年高考刚刚结束,据相关媒体报道,7 日下午,在没有网络和题库支持的情况下,一个名为 Al-Maths 的机器人在 22 分钟内完成了文...

37570
来自专栏AI科技大本营的专栏

输出不详宗教预言,Google翻译为何“水逆”了?

在 Reddit 上,有网友截图显示,在 Google 翻译中当某些语种的词汇翻译成英语时,输出的却是毫无由头的宗教语言。比如键入 19 个 dog,将其从毛利...

8820
来自专栏AI科技评论

开发 | NMT训练成本太高?Google Brain用大规模神经机器翻译架构分析给出解决方案

AI科技评论编者按:十年前,Google Translate发布。当时,这项服务背后的核心算法还是基于短语的机器翻译。 而十年后的今天,更先进的神经网络机器翻译...

370100
来自专栏大数据挖掘DT机器学习

什么是模式识别,与数据挖掘,机器学习关系又如何?

模式识别是对表征事物或现象的各种形式的信息进行处理和分析,以对事物或现象进行描述、辨认、分类和解释的过程,是信息科学和人工智能的重要组成部分。 英文“Patte...

52260
来自专栏机器之心

业界 | 搜狗机器翻译团队获得 WMT 2017 中英机器翻译冠军

搜狗语音交互技术中心 机器之心报道 每年的第三季度都是机器学习相关的顶级学术会议密集召开的时期,今年也不例外。其中,作为自然语言处理领域顶级国际会议之一的 EM...

420130
来自专栏牛客网

算法工程师:学习经验/心得+求职经验算法学习与求职经验学习心得和经验 求职心得和经验

算法学习与求职经验 今天已经是11月初了,找工作的阶段已经进入尾声。回想这半年的时间,充满苦涩与艰辛,有幸拿到了几个offer,腾讯和滴滴的SP,还有百度和华为...

54460
来自专栏AI研习社

Google Brain:NMT训练成本太高?用大规模神经机器翻译架构分析给出解决方案

编者按:十年前,Google Translate发布。当时,这项服务背后的核心算法还是基于短语的机器翻译。 而十年后的今天,更先进的神经网络机器翻译( Neur...

35350
来自专栏程序你好

开源项目ELMo:机器学习在自动翻译中的应用

18440

扫码关注云+社区

领取腾讯云代金券