题解 | #数列重排#

• 先排序
• 再用next_permutation求出所有字典序排列（这里有点疑惑，存在重复数字的应该有出现重复排列，会影响结果吗）
• 枚举当前所有分割情况，判断是否有一个分割情况是合法（这里题意好像也不明确，必须都是升序或都是降序，不能有的升序，有的降序）

#include<bits/stdc++.h>

using namespace std;

vector<int> a = {2, 5, 3, 6, 3, 6, 7, 3, 7, 8};
int cnt;
int up;//升序

// -1 表示可以当成升序或降序，0表示降序，1表示升序，2表示无序
int check(int l, int r) {
    if(l == r) return -1;//升序或降序

    int i;
    for(i = l+1; i <= r; i++) {
        if(a[i-1] != a[i]) break;
    }
    if(i > r) return -1;//升序或降序

    for(i = l+1; i <= r; i++) {
        if(a[i-1] < a[i]) break;
    }
    if(i > r) return 1;//升序

    for(i = l+1; i <= r; i++) {
        if(a[i-1] > a[i]) break;
    }
    if(i > r) return 1;//降序

    return 2;//无序

}

void div() {

    int n = a.size();
    for(int i = 0; i < n-2; i++) {
        for(int j = i+1; j < n-1; j++) {
//                printf("(%d %d) (%d %d) (%d %d)\n", 0, i, i+1, j, j+1, n-1);
            // 必须都是升序或都是降序
            int r1 = check(0,i), r2 = check(i+1, j), r3 = check(j+1, n-1);
            if(r1 == 2 || r2 == 2 || r3 == 2 ) continue;//有一个无序
            // 包含升序和降序的情况
            if(r1 == 0 && r2 == 1) continue;
            if(r1 == 1 && r2 == 0) continue;
            if(r2 == 0 && r3 == 1) continue;
            if(r2 == 1 && r3 == 0) continue;
            if(r1 == 0 && r3 == 1) continue;
            if(r1 == 1 && r3 == 0) continue;
            cnt++; return;//合法情况，结束
        }
    }
}

int main() {

    // 注意使用next_permutation要先sort才能求出所有字典序
    sort(a.begin(), a.end());
    do {
            div();
//            printf("%d\n", cnt);
    }while(next_permutation(a.begin(), a.end()));

    cout << cnt << endl;

    return 0;
}