“九韶杯”河科院程序设计协会第一届程序设计竞赛 D数列重组 next_permutation

“九韶杯”河科院程序设计协会第一届程序设计竞赛 D数列重组  next_permutation

 

题目

原题链接: https://ac.nowcoder.com/acm/contest/13493/D

 

 

---

 

知识点

----boolnext_permutation(BidrectionalIterator first,BidrectionalIterator last)

 

next_permutation对一串数全排列时, 可以用它, 一般搭配do while()

但要注意的是, next_permutation的原理是把数换成逆序, 所以只有原数组排成顺序才会出现完整的全排列

 

#include <iostream>
#include<algorithm>
using namespace std;
int a[3]={1,2,3};

int main()
{
    do  cout << a[0] << a[1] << a[2] << endl; 
    while(next_permutation(a, a+3));//意为排列前3个数
    
    return 0;
}

另: prev_permutation()与此相反, 是将数换成顺序

题意

给出一串数2, 3, 3, 3, 5, 6, 6, 7, 7, 8, 要求将它分成三份, 每份数的数量可以==1, 并且每份必须是单增/单减(中间可以出现几个值相等), 比如(2,2,2)和(1,2,2,3) 和(1,2,2)都可以, 要求输出这样排列的种数

 

题解

代码还是挺好懂的~

 

AC代码

#include <bits/stdc++.h>

using namespace std;
bool cmp(int a,int b){
    return a > b;
}
int a[10]={2, 3, 3, 3, 5, 6, 6, 7, 7, 8};

int main()
{
    long long res = 0; 
    
    do
    {
        bool ok = false;
        for(int i = 0; i <= 7; i ++)//i的值为截取的最后一个数是第几个数(=下标+)
        {
            for(int j = i+1; j <=8; j ++)
            {
                if((is_sorted(a,a+i+1) || is_sorted(a,a+i+1,cmp)) &&
                   (is_sorted(a+i+1,a+j+1) || is_sorted(a+i+1,a+j+1,cmp)) &&
                   (is_sorted(a+j+1,a+10) || is_sorted(a+j+1,a+10,cmp)))
                {
                    ok = 1;
                    break;
                }
            }
            if(ok)    break;
        }
        if(ok)res ++;
        
    }while(next_permutation(a, a+10));
    
    
    cout << res << endl;
    return 0;
}