Educational Codeforces Round 133 (Rated for Div. 2) C. Robot in a Hallway

题目

思路:

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define fi first
#define se second
#define lson p << 1
#define rson p << 1 | 1
const int maxn = 1e6 + 5, inf = 1e18, maxm = 4e4 + 5;
const int N = sqrt(1e9) + 1;
 const int mod = 1e9 + 7;
// const int mod = 998244353;
//const __int128 mod = 212370440130137957LL;
// int a[505][5005];
// bool vis[505][505];

int a[2][maxn], b[maxn];
bool vis[maxn];
string s;
int n, m;

struct Node{
    int val, id;
    bool operator<(const Node &u)const{
        return val < u.val;
    }
};
// Node c[maxn];

int ans[maxn];
int pre[maxn];

int f[maxn][2]; //f[j][i]为从起点开始,蛇皮走位到第j列,第i行的最长等待时间
int g[maxn][2];//g[j][i]为从(i,j)向右开始钩子走位,最后回到(i ^ 1, j)的最长等待时间
//long long ? maxn ? n? m?
void solve(){
    int res = 0;
    int q, k;
    cin >> m;
    // int mx = 0, mn = inf;
	for(int i = 0; i < 2; i++){
		for(int j = 1; j <= m; j++){
            cin >> a[i][j];
        }
    }
    //设在起点等待时间为t,到达(i, j)是第k个到达的格子,那么若t + k >= a[i][j] + 2 - k,
    //(题解为t + k >= a[i][j] + 1, 是因为最后题解答案 + 2 * m,实际是2 * m - 1)
    //则在起点等待t秒后,不考虑其他格子的话,可以顺利到达格子(i, j)
    f[0][0] = f[0][1] = -inf;
    f[1][0] = 0;//起点比较特殊,不适用 t + k >= a[i][j] + 2 - k, 单独更新
    f[1][1] = a[1][1] + 2 - 2;//顺便更新掉
    g[m + 1][0] = g[m + 1][1] = -inf;
    for(int j = 2; j <= m; j++){
        f[j][j % 2] = max({f[j - 1][(j - 1) % 2], a[j % 2][j] + 2 - 2 * j, a[j % 2 ^ 1][j] + 2 - (2 * j - 1)});
        // cout << j << ' ' << j % 2 << ' ' << f[j][j % 2] << '\n';
    }
    
    for(int i = 0; i < 2; i++){
        for(int j = m; j >= 2; j--){//注意j >= 2, 因为当j == 1时,整个路径为钩子,就牵扯到起点,得单独更新
            g[j][i] = max({g[j + 1][i] - 1, a[i][j] + 2 - 1, a[i ^ 1][j] + 2 - 2 * (m - j + 1)});
            // cout << j << ' ' << i << ' ' << g[j][i] << '\n';
        }
    }
    res = inf;
    for(int j = 1; j <= m; j++){
        int tmp = max({0LL, f[j][j % 2], g[j + 1][j % 2] - 2 * j});//拼接 蛇和钩子
        res = min(res, tmp);
    }
    res = min(res, max({0LL, g[2][0] - 1, a[1][1] + 2 - (2 * m)}));//考虑整个路径为钩子的情况
    cout << res + 2 * m - 1 << '\n';
}   
    
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int T = 1;
    cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/514839.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

探索async/await的魔力:简化JavaScript异步编程

&#x1f31f; 前言 欢迎来到我的技术小宇宙&#xff01;&#x1f30c; 这里不仅是我记录技术点滴的后花园&#xff0c;也是我分享学习心得和项目经验的乐园。&#x1f4da; 无论你是技术小白还是资深大牛&#xff0c;这里总有一些内容能触动你的好奇心。&#x1f50d; &#x…

软件设计师28--SQL语言

软件设计师28--SQL语言 考点1&#xff1a;普通查询SQL语言SQL语言 - 查询例题&#xff1a; 考点2&#xff1a;分组查询SQL语言 - 查询例题&#xff1a; 考点3&#xff1a;权限控制SQL语言例题&#xff1a; 考点1&#xff1a;普通查询 SQL语言 SQL语言 - 查询 例题&#xff1a;…

容器安全的防护之道

随着云计算的发展&#xff0c;云原生技术已经成为企业数字化转型的得力武器&#xff0c;如何保障容器安全&#xff0c;已成为企业最关心的问题。为此&#xff0c;德迅蜂巢原生安全平台由德迅云安全自主研发&#xff0c;能够很好集成到云原生复杂多变的环境中&#xff0c;如PaaS…

redis乱码\xac\xed\x00\x05t\x00H解决

发现数据库乱码&#xff1a; 这数据库是来自rdids队列list实现的一个简单队列&#xff0c;停止使用该list的服务&#xff0c;查看里面的值&#xff0c;发现 乱码\xac\xed\x00\x05t\x00H&#xff0c;如下图&#xff1a; 很明发送数据端的问题&#xff0c;检查代码&#xff1a; …

软考高级架构师:嵌入式系统概述

一、AI 讲解 嵌入式操作系统是一种专门设计来管理特定硬件的软件系统。它能够在资源有限的环境中高效运行&#xff0c;常见于嵌入式系统中&#xff0c;如智能家居设备、工业控制系统等。 下面将详细介绍嵌入式系统的架构、初始化过程和部件构成。 嵌入式系统的架构 嵌入式系…

【HTB】Trick 靶场

Trick靶场 地址&#xff1a;https://app.hackthebox.com/machines/477 打靶过程 靶机IP:10.129.227.180 1.信息收集 1.1 nmap 端口扫描 ┌──(root㉿kali)-[~/Desktop] └─# nmap -Pn -sC -sV -p- 10.129.227.180 --min-rate5000 Starting Nmap 7.94SVN ( https://nmap…

探索口腔系统功能架构的演变与未来

随着医疗技术的不断发展和人们对口腔健康的重视&#xff0c;口腔系统的功能架构也在不断演变。从传统的口腔诊疗到数字化的口腔健康管理&#xff0c;口腔系统的功能框架正在经历着翻天覆地的变化。本文将深入探讨口腔系统功能架构的演变历程以及未来发展趋势。 --- 随着社会的…

JavaScript(六)---【回调、异步、promise、Async】

零.前言 JavaScript(一)---【js的两种导入方式、全局作用域、函数作用域、块作用域】-CSDN博客 JavaScript(二)---【js数组、js对象、this指针】-CSDN博客 JavaScript(三)---【this指针&#xff0c;函数定义、Call、Apply、函数绑定、闭包】-CSDN博客 JavaScript(四)---【执…

阿里云弹性计算通用算力型u1实例性能评测,性价比高

阿里云服务器u1是通用算力型云服务器&#xff0c;CPU采用2.5 GHz主频的Intel(R) Xeon(R) Platinum处理器&#xff0c;ECS通用算力型u1云服务器不适用于游戏和高频交易等需要极致性能的应用场景及对业务性能一致性有强诉求的应用场景(比如业务HA场景主备机需要性能一致)&#xf…

某站价值5000的码支付多商户商业版 完美可运营版本PHP源码

一款非常好用的码支付即时到账PHP源码 互站网卖4999 买来之后 模板有点丑 自己更换了的一个好看点的 1.修改数据库 用户名 密码 数据库名 2.后台地址 你的域名/admin 账号admin 密码123456 3.通用的监控APP软件, 反编译一下修改成你平台的名字和图标即可 源码免费…

动规训练2

一、最小路径和 1、题目解析 就是一个人从左上往做下走&#xff0c;每次只能往右或者往下&#xff0c;求他到终点时&#xff0c;路径上数字和最小&#xff0c;返回最小值 2、算法原理 a状态表示方程 小技巧&#xff1a;经验题目要求 用一个二维数组表示&#xff0c;创建一个…

(4)(4.6) Triducer

文章目录 前言 1 安装triducer 2 故障排除 3 参数说明 前言 Triducer 集速度、温度和深度传感器于一体。埃文在这篇 ardupilot.org 博文底部提供了这些说明(Evan at the bottom of this ardupilot.org blog post)。 1 安装triducer 下面的示例提供了在 Pixhawk 上安装 tri…

javaWeb城市公交查询系统的设计与实现

一、选题背景 随着低碳生活的普及&#xff0c;人们更倾向于低碳环保的出行方式&#xff0c;完善公交系统无疑具有重要意义。公交是居民日常生活中最常使用的交通工具之一&#xff0c;伴随着我国经济繁荣和城市人口增长&#xff0c;出行工具的选择也变得越来越重要。政府在公共…

使用vuepress搭建个人的博客(一):基础构建

前言 vuepress是一个构建静态资源网站的库 地址:VuePress 一般来说,这个框架非常适合构建个人技术博客,你只需要把自己写好的markdown文档准备好,完成对应的配置就可以了 搭建 初始化和引入 创建文件夹press-blog npm初始化 npm init 引入包 npm install -D vuepress…

涂鸦 IoT 开发平台产品开发使用教程

产品开发 一、涂鸦 IoT 平台 地址。 什么是涂鸦 IoT 开发平台&#xff1f; 涂鸦 IoT 开发平台支持海量物联网&#xff08;IoT&#xff09;设备、网关、服务、应用连接上云。在 产品开发 阶段&#xff0c;涂鸦 IoT 开发平台提供了多种连接方式&#xff0c;实现设备与 Io…

最新梨花带雨网页音乐播放器

源码简介 最新梨花带雨网页音乐播放器二开优化修复美化版全开源版本源码下载 梨花带雨播放器基于thinkphp6开发的XPlayerHTML5网页播放器前台控制面板,支持多音乐平台音乐解析。二开内容&#xff1a;修复播放器接口问题&#xff0c;把接口本地化&#xff0c;但是集成外链播放…

【系统架构师】-软件架构评估

1、质量属性 1、性能 系统的响应能力&#xff0c;响应时间、吞吐量&#xff0c; 策略&#xff1a;优先级队列、资源调度 2、可用性 系统正常运行的时间比例&#xff08;两次故障之间的时间长度&#xff09;&#xff0c;故障间隔时间&#xff0c; 策略&#xff1a;冗余、心…

JavaScript基础代码练习之翻转数组

一、要求将给定数组 [red, green, blue, pink, purple] 的内容反转存放&#xff0c;并将结果输出到控制台。 二、编写代码 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta name"viewport" cont…

【漏洞复现】通天星CMSV6车载主动安全监控云平台inspect_file接口处存在任意文件上传漏洞

免责声明&#xff1a;文章来源互联网收集整理&#xff0c;请勿利用文章内的相关技术从事非法测试&#xff0c;由于传播、利用此文所提供的信息或者工具而造成的任何直接或者间接的后果及损失&#xff0c;均由使用者本人负责&#xff0c;所产生的一切不良后果与文章作者无关。该…

深度学习评价指标(1):目标检测的评价指标

1. 简述 在计算机视觉/深度学习领域&#xff0c;每一个方向都有属于自己的评价指标。通常在评估一个模型时&#xff0c;只需要计算出相应的评价指标&#xff0c;便可以评估算法的性能。同时&#xff0c;所谓SOTA&#xff0c;皆是基于某一评价指标进行的评估。 接下来&#xff0…