【备战秋招】每日一题:5月13日美团春招第三题:题面+题目思路 + C++/python/js/Go/java带注释

为了更好的阅读体检，为了更好的阅读体检，，可以查看我的算法学习博客第三题-火车调度

在线评测链接:P1288

题目描述

塔子哥是一位火车车厢调度员。

这一天，一列带有 n 个编号车厢的列车进站了，编号为 1\rightarrow n 。但是，这些车厢的编号并不是按从左到右递增的顺序，为了后面的工作方便展开，塔子哥想把火车调整成从左到右递增的顺序，即 [1,2,3,...,n] ，但他只能进行一种操作：首先他要在火车中任意选择两个车厢取出。然后他将两个车厢中较大的放在火车的最右边，较小的放在火车的最左边。

他可以进行无限次这样的操作，他想知道最少需要多少次才能将火车调整为从左到右递增的顺序。

输入描述

第一行是数组的长度： n . 第二行有n个数字p_i (i=1,2,3,...,n)表示从左到右的车厢编号。( 1\leq n\leq 50000,1\leq p_i\leq n)

输出描述

输出一个整数，表示最少需要操作多少次。

样例

输入

7
1 3 5 2 4 6 7

输出

3

说明

第一步选择5，3，第二步选2，6，第三步选1，7。

思路

思维,构造

考虑什么数需要更新位置？

先来考虑 n 为偶数的情况：mid = n/2

记 pos[x] 为数 x 在数组中的位置

将数分为 [1,mid] 和 [mid+1,n] 两部分

  • 对于 [1,mid] 这部分数：找到一个最大的 j，满足存在 j\in[1,mid],k\in[1,mid],j<k,pos[j]>pos[k]，那么 [1,j] 这 j 个数都要更新位置，故这部分需要更新 j 次。

  • 对于 [mid+1,n] 这部分数，找到一个最小的 j ，满足存在 j\in [mid+1,n],k\in[mid+1,n]，j>k,pos[j]<pos[k]，那么 [j+1,n] 这 n-j 个数都要更新位置，故这部分需要更新 n-j 次。

  • 两者取 \max，即\max(j,n-j) 为答案。

对于 n 为奇数的情况，其实就是多了一个中间的数 (n+1)/2。本质没有区别。

时间复杂度：O(n)

类似题目推荐

一开始塔子哥就感觉到这道题目非常的CodeForces风，力扣上没有类似的思维题。后来于某天233大佬成功破案，这就是一道codeforces的原题：CF-1792C

Codefun2000

P1264. 塔子月赛1-第三题-2333的小清新数论题

代码

CPP

#include <bits/stdc++.h>
using namespace std;
​
int main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
​
    int ans = 0;
    if (n & 1) {
        // 奇数情况
        int L = (n + 1) / 2, R = L;
        for (int i = 0; i < n; ++i) {
            if (a[i] == L) {
                // 找到从 L 开始往前递减 1 可以到的最小数 t，从 t 到 L 均不需要更新位置，而从 1 到 t - 1 这些数需要更新位置
                int t = L;
                for (int j = i; j >= 0; --j) {
                    if (a[j] == t) t -= 1;
                }
                ans = max(ans, t);
​
                // 找到从 R 开始往后递增 1 可以到的最大数 t，从 R 到 t 均不需要更新位置，而从 t + 1 到 n 这些数需要更新位置
                t = R;
                for (int j = i; j < n; ++j) {
                    if (a[j] == t) t += 1;
                }
                ans = max(ans, n - t + 1);
            }
        }
        // 奇数情况下，L 和 R 的位置相同，故无需单独考虑 L 的位置在 R 的位置之后这种情况
    } else {
        // 偶数情况
        int L = n / 2, R = L + 1;
        int pL = -1, pR = -1;
        for (int i = 0; i < n; ++i) {
            if (a[i] == L) {
                pL = i;
                // 找到从 L 开始往前递减 1 可以到的最小数 t，从 t 到 L 均不需要更新位置，而从 1 到 t - 1 这些数需要更新位置
                int t = L;
                for (int j = i; j >= 0; --j) {
                    if (a[j] == t) t -= 1;
                }
                ans = max(ans, t);
            }
​
            if (a[i] == R) {
                pR = i;
                // 找到从 R 开始往后递增 1 可以到的最大数 t，从 R 到 t 均不需要更新位置，而从 t + 1 到 n 这些数需要更新位置
                int t = R;
                for (int j = i; j < n; ++j) {
                    if (a[j] == t) t += 1;
                }
                ans = max(ans, n - t + 1);
            }
        }
        // 如果 L 的位置在 R 的后面，则所有的数都要更新位置
        if (pL > pR) {
            ans = n / 2;
        }
    }
​
    cout << ans << "\n";
​
    return 0;
}

python

n = int(input())
a = list(map(int, input().split()))
​
ans = 0
if n % 2 == 1:
    # 奇数情况
    L = (n + 1) // 2
    R = L
    for i in range(n):
        if a[i] == L:
            # 找到从 L 开始往前递减 1 可以到的最小数 t，从 t 到 L 均不需要更新位置，而从 1 到 t - 1 这些数需要更新位置
            t = L
            for j in range(i, -1, -1):
                if a[j] == t:
                    t -= 1
            ans = max(ans, t)
​
            # 找到从 R 开始往后递增 1 可以到的最大数 t，从 R 到 t 均不需要更新位置，而从 t + 1 到 n 这些数需要更新位置
            t = R
            for j in range(i, n):
                if a[j] == t:
                    t += 1
            ans = max(ans, n - t + 1)
else:
    # 偶数情况
    L = n // 2
    R = L + 1
    pL = -1
    pR = -1
    for i in range(n):
        if a[i] == L:
            pL = i
            # 找到从 L 开始往前递减 1 可以到的最小数 t，从 t 到 L 均不需要更新位置，而从 1 到 t - 1 这些数需要更新位置
            t = L
            for j in range(i, -1, -1):
                if a[j] == t:
                    t -= 1
            ans = max(ans, t)
​
        if a[i] == R:
            pR = i
            # 找到从 R 开始往后递增 1 可以到的最大数 t，从 R 到 t 均不需要更新位置，而从 t + 1 到 n 这些数需要更新位置
            t = R
            for j in range(i, n):
                if a[j] == t:
                    t += 1
            ans = max(ans, n - t + 1)
​
    # 如果 L 的位置在 R 的后面，则所有的数都要更新位置
    if pL > pR:
        ans = n // 2
​
print(ans)

Java

import java.util.*;
​
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; ++i) {
            a[i] = sc.nextInt();
        }
​
        int ans = 0;
        if (n % 2 == 1) {
            // 奇数情况
            int L = (n + 1) / 2;
            int R = L;
            for (int i = 0; i < n; ++i) {
                if (a[i] == L) {
                    // 找到从 L 开始往前递减 1 可以到的最小数 t，从 t 到 L 均不需要更新位置，而从 1 到 t - 1 这些数需要更新位置
                    int t = L;
                    for (int j = i; j >= 0; --j) {
                        if (a[j] == t) {
                            t -= 1;
                        }
                    }
                    ans = Math.max(ans, t);
​
                    // 找到从 R 开始往后递增 1 可以到的最大数 t，从 R 到 t 均不需要更新位置，而从 t + 1 到 n 这些数需要更新位置
                    t = R;
                    for (int j = i; j < n; ++j) {
                        if (a[j] == t) {
                            t += 1;
                        }
                    }
                    ans = Math.max(ans, n - t + 1);
                }
            }
            // 奇数情况下，L 和 R 的位置相同，故无需单独考虑 L 的位置在 R 的位置之后这种情况
        } else {
            // 偶数情况
            int L = n / 2;
            int R = L + 1;
            int pL = -1;
            int pR = -1;
            for (int i = 0; i < n; ++i) {
                if (a[i] == L) {
                    pL = i;
                    // 找到从 L 开始往前递减 1 可以到的最小数 t，从 t 到 L 均不需要更新位置，而从 1 到 t - 1 这些数需要更新位置
                    int t = L;
                    for (int j = i; j >= 0; --j) {
                        if (a[j] == t) {
                            t -= 1;
                        }
                    }
                    ans = Math.max(ans, t);
                }
​
                if (a[i] == R) {
                    pR = i;
                    // 找到从 R 开始往后递增 1 可以到的最大数 t，从 R 到 t 均不需要更新位置，而从 t + 1 到 n 这些数需要更新位置
                    int t = R;
                    for (int j = i; j < n; ++j) {
                        if (a[j] == t) {
                            t += 1;
                        }
                    }
                    ans = Math.max(ans, n - t + 1);
                }
            }
            // 如果 L 的位置在 R 的后面，则所有的数都要更新位置
            if (pL > pR) {
                ans = n / 2;
            }
        }
​
        System.out.println(ans);
    }
}

Go

package main
​
import "fmt"
​
func main() {
    var n int
    fmt.Scan(&n)
    a := make([]int, n)
    for i := 0; i < n; i++ {
        fmt.Scan(&a[i])
    }
​
    ans := 0
    if n%2 == 1 {
        // 奇数情况
        L, R := (n+1)/2, (n+1)/2
        for i := 0; i < n; i++ {
            if a[i] == L {
                // 找到从 L 开始往前递减 1 可以到的最小数 t，从 t 到 L 均不需要更新位置，而从 1 到 t - 1 这些数需要更新位置
                t := L
                for j := i; j >= 0; j-- {
                    if a[j] == t {
                        t -= 1
                    }
                }
                ans = max(ans, t)
​
                // 找到从 R 开始往后递增 1 可以到的最大数 t，从 R 到 t 均不需要更新位置，而从 t + 1 到 n 这些数需要更新位置
                t = R
                for j := i; j < n; j++ {
                    if a[j] == t {
                        t += 1
                    }
                }
                ans = max(ans, n-t+1)
            }
        }
        // 奇数情况下，L 和 R 的位置相同，故无需单独考虑 L 的位置在 R 的位置之后这种情况
    } else {
        // 偶数情况
        L, R := n/2, n/2+1
        pL, pR := -1, -1
        for i := 0; i < n; i++ {
            if a[i] == L {
                pL = i
                // 找到从 L 开始往前递减 1 可以到的最小数 t，从 t 到 L 均不需要更新位置，而从 1 到 t - 1 这些数需要更新位置
                t := L
                for j := i; j >= 0; j-- {
                    if a[j] == t {
                        t -= 1
                    }
                }
                ans = max(ans, t)
            }
​
            if a[i] == R {
                pR = i
                // 找到从 R 开始往后递增 1 可以到的最大数 t，从 R 到 t 均不需要更新位置，而从 t + 1 到 n 这些数需要更新位置
                t := R
                for j := i; j < n; j++ {
                    if a[j] == t {
                        t += 1
                    }
                }
                ans = max(ans, n-t+1)
            }
        }
        // 如果 L 的位置在 R 的后面，则所有的数都要更新位置
        if pL > pR {
            ans = n / 2
        }
    }
​
    fmt.Println(ans)
}
​
func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

Js

process.stdin.resume();
process.stdin.setEncoding('utf-8');
let input = '';
process.stdin.on('data', (data) => {
    input += data;
});
process.stdin.on('end', () => {
    const lines = input.trim().split('\n');
    const n = parseInt(lines[0]);
    const a = lines[1].split(' ').map(x => parseInt(x));
​
    let ans = 0;
    if (n % 2 === 1) {
        // 奇数情况
        const L = Math.floor((n + 1) / 2), R = L;
        for (let i = 0; i < n; ++i) {
            if (a[i] === L) {
                // 找到从 L 开始往前递减 1 可以到的最小数 t，从 t 到 L 均不需要更新位置，而从 1 到 t - 1 这些数需要更新位置
                let t = L;
                for (let j = i; j >= 0; --j) {
                    if (a[j] === t) t -= 1;
                }
                ans = Math.max(ans, t);
​
                // 找到从 R 开始往后递增 1 可以到的最大数 t，从 R 到 t 均不需要更新位置，而从 t + 1 到 n 这些数需要更新位置
                t = R;
                for (let j = i; j < n; ++j) {
                    if (a[j] === t) t += 1;
                }
                ans = Math.max(ans, n - t + 1);
            }
        }
        // 奇数情况下，L 和 R 的位置相同，故无需单独考虑 L 的位置在 R 的位置之后这种情况
    } else {
        // 偶数情况
        const L = Math.floor(n / 2), R = L + 1;
        let pL = -1, pR = -1;
        for (let i = 0; i < n; ++i) {
            if (a[i] === L) {
                pL = i;
                // 找到从 L 开始往前递减 1 可以到的最小数 t，从 t 到 L 均不需要更新位置，而从 1 到 t - 1 这些数需要更新位置
                let t = L;
                for (let j = i; j >= 0; --j) {
                    if (a[j] === t) t -= 1;
                }
                ans = Math.max(ans, t);
            }
​
            if (a[i] === R) {
                pR = i;
                // 找到从 R 开始往后递增 1 可以到的最大数 t，从 R 到 t 均不需要更新位置，而从 t + 1 到 n 这些数需要更新位置
                let t = R;
                for (let j = i; j < n; ++j) {
                    if (a[j] === t) t += 1;
                }
                ans = Math.max(ans, n - t + 1);
            }
        }
        // 如果 L 的位置在 R 的后面，则所有的数都要更新位置
        if (pL > pR) {
            ans = Math.floor(n / 2);
        }
    }
​
    console.log(ans);
});

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

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

相关文章

【linux网络配置】多个网卡一起使用，一个网卡连内网，一个网卡连外网

【linux网络配置】多个网卡一起使用，一个网卡连内网，一个网卡连外网

一、问题背景 因为有一个工作站在内网中&#xff0c;但是没有办法联网&#xff08;校园网账户有限&#xff09;。 虽然工作站没有联网&#xff0c;但是我仍然可以通过局域网远程控制工作站&#xff0c;使其访问校园网验证页面实现上网。 当给工作站安装软件或依赖项时&#…
阅读更多...
grpc 实现grpc gateway（window环境）

grpc 实现grpc gateway（window环境）

官网&#xff1a;https://grpc-ecosystem.github.io/grpc-gateway/ github&#xff1a;https://github.com/grpc-ecosystem/grpc-gateway grpc gateway的原理官网有介绍。总结一下就是&#xff1a; gRPC-Gateway帮助你同时以gRPC和RESTful风格提供你的API。grpc-gateway旨在为您…
阅读更多...
【Linux】linux下使用命令修改jar包内某一个文件中的内容并重新运行jar程序

【Linux】linux下使用命令修改jar包内某一个文件中的内容并重新运行jar程序

linux下使用命令修改jar包内某一个文件中的内容并重新运行jar程序 一、背景描述二、vi命令编辑三、启动程序四、拓展--启动脚本 一、背景描述 需求&#xff1a;发现线上的 iotp-irsb-server-v1.0.0.2.jar 包中配置文件的日志级别配置错误&#xff0c;需要在线修改jar包中文件的…
阅读更多...
MFC的定义和实际操作方法

MFC的定义和实际操作方法

我是荔园微风&#xff0c;作为一名在IT界整整25年的老兵&#xff0c;今天从另一个角度来看一下MFC。 完整的应用一般由四个类组成&#xff1a;CWinApp应用类&#xff0c;CFrameWnd窗口框架类&#xff0c;CDocument文档类&#xff0c;CView视类 过程&#xff1a;CWinApp创建CF…
阅读更多...
ubuntu iptables开机自启动

ubuntu iptables开机自启动

一、配置ubuntu路由转发 用在一台电脑有多个网卡的情形下&#xff0c;一个网卡5网段、一个网卡8网段&#xff0c;8网段是网络出口&#xff0c;所以5网段的设备需要入网的话&#xff0c;要路由转发。 sudo iptables -t nat -A POSTROUTING -s 192.168.5.0/24 -j SNAT --to-sou…
阅读更多...
STM32速成笔记—概述

STM32速成笔记—概述

文章目录 前言一、专栏简介二、前期准备三、编程规范以及程序架构简介1. 编程规范2. 程序架构 四、STM32F103ZET6简介五、程序模板六、ST-Link调试6.1 硬件连接6.2 Keil配置6.3 下载调试 前言 本人技术菜鸟一枚&#xff0c;2022年大学毕业&#xff0c;大学加入老师实验室&#…
阅读更多...
chatgpt赋能python：如何在Python中创建模块：完整指南

chatgpt赋能python：如何在Python中创建模块：完整指南

如何在Python中创建模块&#xff1a;完整指南 如果你是一位Python开发者&#xff0c;你肯定需要用到模块。模块使得代码更容易组织和管理&#xff0c;并且可以复用许多代码片段&#xff0c; 提高代码的可重用性。在Python中&#xff0c;模块是一组相关函数&#xff0c;方法和变…
阅读更多...
oracle expdp导致system表空间满

oracle expdp导致system表空间满

今天下午&#xff0c;项目经理反馈有套11204版本数据库无法使用了&#xff0c;立刻登录检查环境发现SYSTEM表空间使用率99.99%了 TABLESPACE_NAME MAXSIZE_MB ACTUALSIZE_MB USED_MB FREESPACE_MB SPACE USAGE ----------------- ---------- ------------- ---------- …
阅读更多...
Trace32 SRST和TRST、system.attach 和 system.up的区别

Trace32 SRST和TRST、system.attach 和 system.up的区别

目录 TRST-Resets the JTAG TAP controller and the CPU internal debug logic SRST- Resets the CPU core and peripherals SYStem.Mode Down SYStem.Mode Nodebug SYStem.Mode Prepare SYStem.Mode Go SYStem.Mode Attach SYStem.Mode StandBy SYStem.Mode Up 下图为…
阅读更多...
ProGuard 进阶系列（二）配置解析

ProGuard 进阶系列（二）配置解析

书接上文&#xff0c;从开源库中把代码下载到本地后&#xff0c;就可以在 IDE 中进行运行了。从 main 方法入手&#xff0c;可以看到 ProGuard 执行的第一步就是去解析参数。本文的内容主要分析源码中我们配置的规则解析的实现。 在上一篇文章末尾&#xff0c;在 IDE 中&#x…
阅读更多...
大数据Doris（三十七）：Spark Load导入HDFS数据

大数据Doris（三十七）：Spark Load导入HDFS数据

文章目录 Spark Load导入HDFS数据 一、准备HDFS数据 二、创建Doris表 三、创建Spark Load导入任务
阅读更多...
【Reids】搭建主从集群以及主从数据同步原理

【Reids】搭建主从集群以及主从数据同步原理

目录 一、搭建主从集群 1、介绍 2、搭建 二、数据同步原理 1、全量同步 2、主节点如何判断是不是第一次连接 3、增量同步 4、优化主从数据同步 一、搭建主从集群 1、介绍 单节点的Redis并发能力存在上限&#xff0c;要提高并发能力就需要搭建主从集群&#xff0c;实现…
阅读更多...
【LLM GPT】李宏毅大型语言模型课程

【LLM GPT】李宏毅大型语言模型课程

目录 1 概述1.1 发展历程1.2 预训练监督学习预训练的好处 1.3 增强式学习1.4 对训练数据的记忆1.5 更新参数1.6 AI内容检测1.7 保护隐私1.8 gpt和bert穷人怎么用gpt 2 生成式模型2.1 生成方式2.1.1 各个击破 Autoregressive2.1.2 一次到位 Non-autoregressive2.1.3 两者结合 2.…
阅读更多...
RabbitMQ虚拟主机无法启动的原因和解决方案

RabbitMQ虚拟主机无法启动的原因和解决方案

RabbitMQ虚拟主机无法启动的原因和解决方案 摘要&#xff1a; RabbitMQ是一个广泛使用的开源消息代理系统&#xff0c;但在使用过程中可能会遇到虚拟主机无法启动的问题。本文将探讨可能导致该问题的原因&#xff0c;并提供相应的解决方案&#xff0c;以帮助读者解决RabbitMQ虚…
阅读更多...
第五章 模型篇： 模型保存与加载

第五章 模型篇： 模型保存与加载

参考教程&#xff1a; https://pytorch.org/tutorials/beginner/basics/saveloadrun_tutorial.html 文章目录 pytorch中的保存与加载torch.save()torch.load()代码示例 模型的保存与加载保存 state_dict()nn.Module().load_state_dict()加载模型参数保存模型本身加载模型本身 c…
阅读更多...
K8s 中 port， targetPort， NodePort的区别

K8s 中 port， targetPort， NodePort的区别

看1个例子&#xff1a; 我们用下面命令去创建1个pod2&#xff0c; 里面运行的是1个nginx kubectl create deployment pod2 --imagenginx当这个POD被创建后&#xff0c; 其实并不能被外部访问&#xff0c; 因为端口映射并没有完成. 我们用下面这个命令去创建1个svc &#xff…
阅读更多...
chatgpt赋能python：Python怎样让画笔变粗

chatgpt赋能python：Python怎样让画笔变粗

Python怎样让画笔变粗 Python是一门强大的编程语言&#xff0c;不仅适用于数据分析和机器学习等领域&#xff0c;也可以用来进行图像处理。在Python中&#xff0c;我们可以使用Pillow库来进行图像操作。在本篇文章中&#xff0c;我们将介绍如何使用Python和Pillow来让画笔变粗…
阅读更多...
vue2_markdown的内容目录生成

vue2_markdown的内容目录生成

文章目录 ⭐前言⭐引入vue-markdown&#x1f496; 全局配置&#x1f496; 渲染选项&#x1f496; 取出markdown的标题层级 ⭐结束 ⭐前言 大家好&#xff01;我是yma16&#xff0c;本文分享在vue2的markdown文本内容渲染和目录生成 背景&#xff1a; 优化个人博客功能&#xf…
阅读更多...
delphi的ARM架构支持与System.Win.WinRT库

delphi的ARM架构支持与System.Win.WinRT库

delphi的ARM架构支持与System.Win.WinRT库 目录 delphi的ARM架构支持与System.Win.WinRT库 一、WinRT 二、delphi的System.Win.WinRT库 2.1、支持ARM芯片指令 2.2、基于WinRT技术的特点 2.3、所以使用默认库而未经转化的服务端应用并不支持ARM架构服务器 2.4、对默认库…
阅读更多...
【Linux】初步认识Linux系统

【Linux】初步认识Linux系统

Linux 操作系统 主要作用是管理好硬件设备&#xff0c;并为用户和应用程序提供一个简单的接口&#xff0c;以便于使用。 作为中间人&#xff0c;连接硬件和软件 常见操作系统 桌面操作系统 WindowsmacOsLinux 服务器操作系统 LinuxWindows Server 嵌入式操作系统 Linux …
阅读更多...
最新文章

Copyright @ 2022~2023