题目思路

核心:让最小值暴露在栈顶然后弹出去。

思路:

1.求两个栈的最小值并确定该最小值所在的栈

2.通过操作1让最小值暴露在栈顶

3.执行操作2

上述三步反复进行n步即可

代码

Java代码

import java.util.*;

public class Main {
    // 获取最小值
    public static int getMin (Stack<Integer> a){
        Stack<Integer> c = new Stack<>();
        int mxa = 10000000;
        // 将栈导出到临时栈c中，同时取最小值
        while (a.empty() == false){
            mxa = Math.min(mxa , (Integer)a.peek());
            c.push(a.peek());
            a.pop();
        }
        // c -> a
        while (c.empty() == false){
            a.push(c.peek());
            c.pop();
        }
        return mxa;
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int x = in.nextInt();
        int y = in.nextInt();
        // 开两个栈模拟该过程
        Stack<Integer> a = new Stack<>();
        Stack<Integer> b = new Stack<>();
        for (int i = 1 ; i <= x ; i++){
            int s = in.nextInt();
            a.push(s);
        }
        for (int i = 1 ; i <= y ; i++){
            int s = in.nextInt();
            b.push(s);
        }
        int ans = 0;
        // 总共会有n轮
        // 每一轮先1.找出栈中的最小值以及其所在的栈 2.将最小值上面的所有数pop到另外一个栈中去
        for (int i = 1 ; i <= n ; i++){
            //选择栈的最小值
            int mxa = getMin(a);
            int mxb = getMin(b);
            // 判断在哪个栈
            if (mxa == Math.min(mxa , mxb)){
                // 将最小值上面的所有数pop到另外一个栈中去
                while ((Integer)a.peek() != mxa){
                    b.push(a.peek());
                    a.pop();
                    ans++;
                }
                a.pop();
                ans++;
            }else {
                // 将最小值上面的所有数pop到另外一个栈中去
                while ((Integer)b.peek() != mxb){
                    a.push(b.peek());
                    b.pop();
                    ans++;
                }
                b.pop();
                ans++; 
            }
        }
        System.out.println(ans);
    }
}

C++代码

#include <bits/stdc++.h>
using namespace std;

// 获取最小值
int getMin (stack<int> a) {
    stack<int> c ;
    int mxa = 10000000;
    // 将栈导出到临时栈c中，同时取最小值
    while (a.empty() == false) {
        mxa = min(mxa , a.top());
        c.push(a.top());
        a.pop();
    }
    // c -> a
    while (c.empty() == false) {
        a.push(c.top());
        c.pop();
    }
    return mxa;
}
int main()
{
    int n, x, y;
    cin >> n >> x >> y;
    stack<int> a;
    stack<int> b;
    for (int i = 1 ; i <= x ; i++) {
        int s ;
        cin >> s;
        a.push(s);
    }
    for (int i = 1 ; i <= y ; i++) {
        int s ;
        cin >> s;
        b.push(s);
    }
    int ans = 0;
    // 总共会有n轮
    // 每一轮先1.找出栈中的最小值以及其所在的栈 2.将最小值上面的所有数pop到另外一个栈中去
    for (int i = 1 ; i <= n ; i++) {
        //选择栈的最小值
        int mxa = getMin(a);
        int mxb = getMin(b);
        // 判断在哪个栈
        if (mxa == min(mxa , mxb)) {
            // 将最小值上面的所有数pop到另外一个栈中去
            while ((int)a.top() != mxa) {
                b.push(a.top());
                a.pop();
                ans++;
            }
            a.pop();
            ans++;
        } else {
            // 将最小值上面的所有数pop到另外一个栈中去
            while ((int)b.top() != mxb) {
                a.push(b.top());
                b.pop();
                ans++;
            }
            b.pop();
            ans++;
        }
    }
    cout<<ans<<endl;
}

Python代码

def getMin(a):
    c = []
    mxa = 1000000000
    while len(a) > 0:
        mxa = min(mxa, a[len(a)-1])
        c.append(a[len(a)-1])
        a.pop()
    while len(c) > 0:
        a.append(c[len(c)-1])
        c.pop()
    return mxa


n, x, y = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ans = 0
for i in range(n):
    mxa = getMin(a)
    mxb = getMin(b)
    if (mxa == min(mxa, mxb)):
        while a[len(a)-1] != mxa:
            b.append(a[len(a)-1])
            a.pop()
            ans += 1
        a.pop()
        ans += 1
    else:
        while b[len(b)-1] != mxb:
            a.append(b[len(b)-1])
            b.pop()
            ans += 1
        b.pop()
        ans += 1
print(ans)

Js代码

process.stdin.resume();
process.stdin.setEncoding('utf-8');
let input = '';

process.stdin.on('data', (data) => {
	input += data;
	return;
});
process.stdin.on('end', () => {
    function getMin(a) {
    let c=new Array();
    let mxa = 10000000;
    // 将栈导出到临时栈c中，同时取最小值
    while (a.length>0) {
        mxa = Math.min(mxa , a[a.length-1]);
        c.push(a[a.length-1]);
        a.pop();
    }
    // c -> a
    while (c.length>0) {
        a.push(c[c.length-1]);
        c.pop();
    }
    return mxa;
}
    let n, x, y;
    input=input.split('\n');
    n=Number(input[0].split(' ')[0]);
    x=Number(input[0].split(' ')[1]);
    y=Number(input[0].split(' ')[2]);
    let a=new Array();
    let b=new Array();
    for (let i = 1 ; i <= x ; i++) {
        let s=Number(input[1].split(' ')[i-1]);
        a.push(s);
    }
    for (let i = 1 ; i <= y ; i++) {
        let s =Number(input[2].split(' ')[i-1]);
        b.push(s);
    }
    let ans = 0;
    // 总共会有n轮
    // 每一轮先1.找出栈中的最小值以及其所在的栈 2.将最小值上面的所有数pop到另外一个栈中去
    for (let i = 1 ; i <= n ; i++) {
        //选择栈的最小值
        let mxa = getMin(a);
        let mxb = getMin(b);
        // 判断在哪个栈
        if (mxa == Math.min(mxa , mxb)) {
            // 将最小值上面的所有数pop到另外一个栈中去
            while (a[a.length-1] != mxa) {
                b.push(a[a.length-1]);
                a.pop();
                ans++;
            }
            a.pop();
            ans++;
        } else {
            // 将最小值上面的所有数pop到另外一个栈中去
            while (b[b.length-1] != mxb) {
                a.push(b[b.length-1]);
                b.pop();
                ans++;
            }
            b.pop();
            ans++;
        }
    }
    console.log(ans);
})

题目内容

小美刚学完栈这个数据结构，觉得非常的神奇。现在作为acm的预选队员之一，他被学长的一个问题给问趴下了。三天没有任何进展，你能帮帮他吗？

“栈(stack)又名堆栈,它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。

小美拿到了两个栈，现在需要将两个栈里面的元素合并为一个n排列。(也就是1~n各出现一次)

现在小美允许有两个操作:

1.选择其中一个栈并弹出栈顶。但是被弹出的元素必须要是两个栈之间的最小值

2.将其中一个栈的栈顶元素弹出，之后放入另外一个栈的栈顶。

求能够完成任务最小操作次数

输入描述

第一行为$n$，$sz_1$,$sz_2$。$n$即为要组成的$n$排列大小，$sz_1$,$sz_2$为两个栈的大小，其中$0<n<1000$,$sz_1+sz_2=n$

第二行$sz_1$个整数$d(0<d<=n)$，表示第一个栈从栈底到栈顶的$sz_1$个元素

第三行$sz_2$个整数$d(0<d<=n)$，表示第二个栈从栈底到栈顶的$sz_2$个元素

样例

输入

4 2 2
1 3
4 2

输出

6