SP12150题解

· · 题解

这道题看起来很难，其实你只要认识这个东西：

next_permutation 全排列函数

就很好做了，如果不会用的话自行百度一下其实是我懒

题目的要求就是遍历输入的数组成的全排列的下一个，所以用全排列函数是真的香

全排列函数基本用法

（1） next_permutation ：求下一个排列组合　

1.函数模板：

next_permutation(arr, arr+size);

2.参数说明：

arr ： 数组名

size ：数组元素个数

3.函数功能： 返回值为 bool 类型，当当前序列不存在下一个排列时，函数返回 false ，否则返回 true ，排列好的数在数组中存储

4.注意：在使用前需要对欲排列数组按升序排序，否则只能找出该序列之后的全排列数。比如，如果数组num初始化为 231 ，那么输出就变为了： 231

（2） prev_permutation ：求上一个排列组合

1.函数模板：

prev_permutation(arr, arr+size);

2.参数说明：

arr ：数组名

size ：数组元素个数

3.函数功能： 返回值为 bool 类型，当当前序列不存在上一个排列时，函数返回 false ，否则返回 true

4.注意：在使用前需要对欲排列数组按降序排序，否则只能找出该序列之后的全排列数。

代码实现

代码（未 ac ，交上一直显示 waiting ）：

#include<bits/stdc++.h>
using namespace std;
int a[100010],t,n;//a数组存输入的数 
int pd()//判断是否是最后一个 
{
    for(int i=1;i<n;i++)
        if(a[i]<a[i+1])//只要前一位比后一位小就肯定不是最大的 
        return 1;//返回判断结果 
    return 0;
}
int main()
{
    cin>>t;//输入测试几组数据 
    while(t--)
    {
        memset(a,0,sizeof(a));//清零 
        cin>>n;
        for(int i=1;i<=n;i++)
            cin>>a[i];//输入数据 
        next_permutation(a+1,a+n+1);//全排列函数 
        if(pd()==1)//判断一下 
        {
            for(int i=1;i<=n;i++)//输出 
            cout<<a[i];
            cout<<endl;
        }
        else cout<<"-1"<<endl;//当前组合是最大的就输出-1 
    }
    return 0;//好习惯 
}