2021年CS保研经历（五）：北航计算机学院、武汉大学数学与统计学院、华科计算机科学与技术学院

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<queue>
#include<stack>
#include<vector>
#include<sstream>
#include<unordered_map>
#include<unordered_set>
using namespace std;

struct node {
    int val;
    int ind;
    node(int val, int ind):val(val), ind(ind){}
};

vector<node*> A, B;  //栈 
int n;
int cnt = 0;

int find(vector<node*>& v) {  //寻找一个栈中最小值的编号 
    if(v.size() == 0) {
        return -1;
    }
    int ind = 0;
    int n = v.size();
    int _min = v[0]->val;
    int idc = v[0]->ind;
    for(int i = 1; i < n; i++) {
        if(v[i]->val < _min) {
            _min = v[i]->val;
            idc = v[i]->ind;
            ind = i;
        }else if(v[i]->val == _min && v[i]->ind < idc) {  //相同则选择序号小的 
            _min = v[i]->val;
            idc = v[i]->ind;
            ind = i;
        }
    }
    return ind;
}

int main() {
    int x;
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> x;
        node* t = new node(x, i);
        A.push_back(t);
    }
    int id = find(A);
    //先将A中最小值输出 
    for(int i = A.size() - 1; i > id; i--) {
        B.push_back(A[i]);
        A.pop_back();
        cnt++;
    } 
    cout << A[id]->val << " ";  //输出最小值
    A.pop_back();
    cnt++;
    while(A.size() != 0 || B.size() != 0) {
        //从AB中各自找最小值
        int x1 = find(A), x2 = find(B);
        if(x2 == -1) {
            //只输出A
            for(int i = A.size() - 1; i > x1; i--) {
                B.push_back(A[i]);
                A.pop_back();
                cnt++;
            }
            cout << A[x1]->val << " ";
            A.pop_back();
            cnt++;
        }else if(x1 == -1) {
            for(int i = B.size() - 1; i > x2; i--) {
                A.push_back(B[i]);
                B.pop_back();
                cnt++;
            }
            cout << B[x2]->val << " ";
            B.pop_back();
            cnt++;
        }else if(A[x1]->val < B[x2]->val || (A[x1]->val == B[x2]->val && A[x1]->ind < B[x2]->ind)) {
            //将A中x1前弹出
            for(int i = A.size() - 1; i > x1; i--) {
                B.push_back(A[i]);
                A.pop_back();
                cnt++;
            }
            cout << A[x1]->val << " ";
            A.pop_back();
            cnt++;
        }else if(A[x1]->val > B[x2]->val || (A[x1]->val == B[x2]->val &&A[x1]->ind > B[x2]->ind)){
            //将B中x2前弹出
            for(int i = B.size() - 1; i > x2; i--) {
                A.push_back(B[i]);
                B.pop_back();
                cnt++;
            }
            cout << B[x2]->val << " ";
            B.pop_back();
            cnt++;
        }
    }
    cout << endl;
    cout << cnt;
    return 0;
}
/*
8
86 25 -200 500 301 25 43 78
*/