【备战秋招】每日一题: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

输出

说明

第一步选择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) // 2R = Lfor i in range(n):if a[i] == L:# 找到从 L 开始往前递减 1 可以到的最小数 t，从 t 到 L 均不需要更新位置，而从 1 到 t - 1 这些数需要更新位置t = Lfor j in range(i, -1, -1):if a[j] == t:t -= 1ans = max(ans, t)
# 找到从 R 开始往后递增 1 可以到的最大数 t，从 R 到 t 均不需要更新位置，而从 t + 1 到 n 这些数需要更新位置t = Rfor j in range(i, n):if a[j] == t:t += 1ans = max(ans, n - t + 1)
else:# 偶数情况L = n // 2R = L + 1pL = -1pR = -1for i in range(n):if a[i] == L:pL = i# 找到从 L 开始往前递减 1 可以到的最小数 t，从 t 到 L 均不需要更新位置，而从 1 到 t - 1 这些数需要更新位置t = Lfor j in range(i, -1, -1):if a[j] == t:t -= 1ans = max(ans, t)
if a[i] == R:pR = i# 找到从 R 开始往后递增 1 可以到的最大数 t，从 R 到 t 均不需要更新位置，而从 t + 1 到 n 这些数需要更新位置t = Rfor j in range(i, n):if a[j] == t:t += 1ans = 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 intfmt.Scan(&n)a := make([]int, n)for i := 0; i < n; i++ {fmt.Scan(&a[i])}
ans := 0if n%2 == 1 {// 奇数情况L, R := (n+1)/2, (n+1)/2for i := 0; i < n; i++ {if a[i] == L {// 找到从 L 开始往前递减 1 可以到的最小数 t，从 t 到 L 均不需要更新位置，而从 1 到 t - 1 这些数需要更新位置t := Lfor j := i; j >= 0; j-- {if a[j] == t {t -= 1}}ans = max(ans, t)
// 找到从 R 开始往后递增 1 可以到的最大数 t，从 R 到 t 均不需要更新位置，而从 t + 1 到 n 这些数需要更新位置t = Rfor 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+1pL, pR := -1, -1for i := 0; i < n; i++ {if a[i] == L {pL = i// 找到从 L 开始往前递减 1 可以到的最小数 t，从 t 到 L 均不需要更新位置，而从 1 到 t - 1 这些数需要更新位置t := Lfor 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 := Rfor 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);
});