OJ测试，排队照相问题

Question

排队照相问题
时间限制: 1000 ms内存限制: 2048 KB
问题描述
N（N为偶数）个高矮不同的人排成两排照相，要求每一排都是从矮到高排列，而第二排每个人比第一排对应的人要高，列出所有可能的结果。
输入格式
第一行正整数N（0<N<100）
第二行第一个人的身高h1
第三行第二个人的身高h2
…
第N+1行第N个人的身高hN
输出格式
1.每种情况占据一行；
2.将第一排按照排队顺序输出身高，然后将第二排按照排队顺序输出身高；
3.身高之间加空格（第二排最后一人后面为换行符，无空格），两排之间不加换行符（第一排最后一人与第二排第一人之间为空格）。
4.最后统计所有情况数目并输出。
输入样例
4
161
162
164
163
输出样例
161 162 163 164
161 163 162 164
2

或者下列输出也正确（即不同情况之间可交换顺序）：
161 163 162 164
161 162 163 164
2
提示
1.使用<stdio.h>中的scanf，printf。它们比中的cin, cout更快。
样例输入有两种排队方式，每种排队方式输出的顺序如图中红线所示：

其中，第一种排队方式对应输出如图所示，第二种同理。

2.每种情况输出完成后要换行。
3.在输出时，不同情况的输出先后顺序不影响答案的正确性。
思路提示
1.把最小身高放在第一排首位
2.选择一个合适的身高放在第二排首位
3.根据上述两个步骤进行递归操作

Answer 1

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int cnt = 0;

bool compare(int a, int b) {
    return a < b;
}

void printResult(const vector<int>& line1, const vector<int>& line2) {
    for(int i=0; i<line1.size(); i++) {
        cout << line1[i] << " ";
    }
    cout << endl;
    for(int i=0; i<line2.size(); i++) {
        cout << line2[i] << " ";
    }
    cout << endl;
    cnt++;
}

void arrange(const vector<int>& heights, vector<int>& line1, vector<int>& line2, int curPos) {
    if(curPos >= heights.size()) {
        printResult(line1, line2);
        return;
    }
    int curHeight = heights[curPos];
    line1.push_back(curHeight);
    sort(line1.begin(), line1.end(), compare);
    for(int i=curPos+1; i<heights.size(); i++) {
        line2.push_back(heights[i]);
        arrange(heights, line1, line2, i+1);
        line2.pop_back();
    }
    line1.pop_back();
}

int main() {
    int N;
    cin >> N;
    vector<int> heights(N);
    for(int i=0; i<N; i++) {
        cin >> heights[i];
    }
    vector<int> line1, line2;
    arrange(heights, line1, line2, 0);
    cout << cnt << endl;
    return 0;
}