“九韶杯”河科院程序设计协会第一届程序设计竞赛 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;
}