Special Permutation 构造，min

Special Permutation 构造，min

题意 ：

• 构造一个n（偶数）的全排列，使得全排列的前半部分最小值等于a，后半部分最大值等于b，如果不能构造，则输出-1

思路一 ：

• 直接构造，将a放最前，b放最后，中间从大到小放，然后构造后判断是否合法，不合法则直接-1
• *min_element表示最小元素，记得加头文件
• cout << p[i] << " n"[i == n - 1] 表示只有在i == n - 1才输出n否则输出空格

#include 
#include 
#include 
#include 
#define pb push_back
#define fi first;
#define se second;

using namespace std;

void solve()
{
    int n, a, b;
    cin >> n >> a >> b;
    vector p{a};
    for (int i = n; i >= 1; i -- )
    {
        if (i == a || i == b) continue;
        p.pb(i);
    }
    p.pb(b);
    
    if (*min_element(p.begin(), p.begin() + n / 2) == a && *max_element(p.begin() + n / 2, p.end()) == b)
    {
        for (int i = 0; i < n; i ++ )
            cout << p[i] << " n"[i == n - 1];
    }
    else
    {
        cout << -1 << endl;
    }
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    int _ = 1;
    cin >> _;
    
    while (_ -- )
    {
        solve();
    }
    return 0;
}

思路二 ：

• 就en构造，发现这个做法太累赘了，比赛的时候边界还卡了很久
• 算边界的时候，忘记减去边界中的另一个空点了

#include 
#include 
#include 
#define pb push_back
#define fi first;
#define se second;
 
using namespace std;
 
void solve()
{
    int n, a, b;
    cin >> n >> a >> b;
    if (a > b)
    {
        if (b != n / 2 || n - a + 1 != n / 2)
        {
            cout << -1 << endl;
            return ;
        }
        for (int i = a; i <= n; i ++ ) cout << i << ' ';
        for (int i = 1; i <= b; i ++ ) cout << i << ' ';
        cout << endl;
    }
    else
    {
        if (n - a < n / 2 || b - 1 < n / 2)
        {
            cout << -1 << endl;
            return ;
        }
        for (int i = a; i <= a - n / 2 + b - 1; i ++ ) cout << i << ' ';
        for (int i = b + 1; i <= n; i ++ ) cout << i << ' ';
        for (int i = 1; i <= a - 1; i ++ ) cout << i << ' ';
        for (int i = a - n / 2 + b; i <= b; i ++ ) cout << i << ' ';
        cout << endl;
    }
}
 
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    int _ = 1;
    cin >> _;
    
    while (_ -- )
    {
        solve();
    }
    return 0;
}