题目描述
小明同学最近喜欢上了排列组合，但是现在有这样的一道题把他难住了，已知有一组数字（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）三组所以该序列为满足题意的一种排列方式。
思路
全排列后，暴力枚举所有分割点，判断是否存在一种分割方式，使得三个部分都是有序的。
AC代码
#include<iostream>
#include<algorithm>
using namespace std;
int a[10] = {2,5,3,6,3,6,7,3,7,8};
int cnt = 0;
bool comp(int a,int b){
return a>b;
}
int main(){
sort(a,a+10);
do{
bool is_break = false;
for(int i=1;i<=8;i++){
for(int j=i+1;j<=9;j++){
if((is_sorted(a,a+i)||is_sorted(a,a+i,comp))&&
(is_sorted(a+i,a+j)||is_sorted(a+i,a+j,comp))&&
(is_sorted(a+j,a+10)||is_sorted(a+j,a+10,comp))){
is_break = true;
cnt++;
break;
}
}
if(is_break){
break;
}
}
}while(next_permutation(a,a+10));
cout<<cnt<<endl;
}注意
i和j的取值范围要注意。
函数is_sorted()和函数next_permutation()、sort()一样，第二个参数是末尾的后一位。（包含第一个参数，不包含第二个参数）
一共10个数，最极限是分成8，1，1。
所以i<=8;j<=9。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/103322.html
