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

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

在线评测链接:P1288

题目描述

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

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

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

输入描述

第一行是数组的长度： n . 第二行有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，满足存在 ，那么 [1,j] 这 j 个数都要更新位置，故这部分需要更新 j 次。

• 对于 [mid 1,n] 这部分数，找到一个最小的 j ，满足存在 ，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);
});

这篇好文章是转载于：学新通技术网