对于一种排序 只要有某种切分 使得三部分满足性质即可

题目描述

小明同学最近喜欢上了排列组合，但是现在有这样的一道题把他难住了，已知有一组数字（2，5，3，6，3，6，7，3，7，8）共10个，对于这组数字进行排列后，可以将排列好的数字分为三个部分，且三个部分都是分别有序的（升序或逆序），小明想知道能够有满足条件的多少种排列方式?

备注

例如对于重新排列后的一种序列(2, 3, 3, 3, 5, 6, 6, 7, 7, 8)可以分为（2）（3，3，3）（5，6，6，7，7，8）三组或（2，3，3）（3，5，6，6）（7，7，8）三组所以该序列为满足题意的一种排列方式。

双指针 + 全排列

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

int a[]={2,5,3,6,3,6,7,3,7,8};

bool check(int l,int r){
    if(l == r)return true;
    int i;
    for(i = l;i < r;i++)
        if(a[i] > a[i + 1])break;  

    if(i == r)return true;

    for(i = l;i < r;i++)   
        if(a[i] < a[i + 1])break;   

    if(i == r)return true;
    return false; 
}


int main()
{
    sort(a,a+10);
    int cnt=0;
    do {
         int flag=0;
         for(int i=0;i<=7;i++)
         {
             for(int j=i+1;j<9;j++)
             {
                if( check(0,i) && check(i+1,j) && check(j+1,9) ) 
                    flag=1;
             }
         }
         if(flag==1) cnt++;
    }while(next_permutation(a,a+10));

    cout << cnt << endl;
}