【每日一题20】AcWing 420. 火星人

发表于 更新于 分类于 Valine：
本文字数： 77 阅读时长 ≈ 1 分钟

Day20 AcWing 420. 火星人

思路

  1. next_permutation 全排列

代码

next_permutation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<bits/stdc++.h>
using namespace std;

const int N=10010;

int n,m;
int q[N];

int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)  scanf("%d",&q[i]);
    while(m--) next_permutation(q,q+n);
    for(int i=0;i<n;i++) printf("%d ",q[i]);
    
    return 0;
}
手动实现next_permutation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 10010;

int n, m;
int q[N];

int main()
{
    scanf("%d%d", &n, &m);

    for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);

    while (m -- )
    {
        int k = n - 1;
        while (q[k - 1] > q[k]) k -- ;
        k -- ;
        int t = k;
        while (t + 1 < n && q[t + 1] > q[k]) t ++ ;
        swap(q[t], q[k]);
        reverse(q + k + 1, q + n);
    }

    for (int i = 0; i < n; i ++ ) printf("%d ", q[i]);

    return 0;
}