P1017

-题目回顾-

人类终于登上了火星的土地并且见到了神秘的火星人。人类和火星人都无法理解对方的语言，但是我们的科学家发明了一种用数字交流的方法。这种交流方法是这样的，首先，火星人把一个非常大的数字告诉人类科学家，科学家破解这个数字的含义后，再把一个很小的数字加到这个大数上面，把结果告诉火星人，作为人类的回答。

火星人用一种非常简单的方式来表示数字――掰手指。火星人只有一只手，但这只手上有成千上万的手指，这些手指排成一列，分别编号为 1,2,3,⋯。火星人的任意两根手指都能随意交换位置，他们就是通过这方法计数的。

一个火星人用一个人类的手演示了如何用手指计数。如果把五根手指――拇指、食指、中指、无名指和小指分别编号为1,2,3,4 和 5，当它们按正常顺序排列时，形成了 5 位数 12345，当你交换无名指和小指的位置时，会形成 5 位数 12354，当你把五个手指的顺序完全颠倒时，会形成 54321，在所有能够形成的120 个 5 位数中，12345 最小，它表示 1；12354 第二小，它表示 2；54321 最大，它表示 120。

-分析-

输出n个数全排列的第x个排列

-代码-

#include <bits/stdc++.h>
using namespace std;
int main()//by AGOMG
{
    int n, num[10005], x;
    cin >> n >> x;
    for (int i = 1; i <= n; i++)
        cin >> num[i];
    for(int i = 1; i <= x; i++)
        next_permutation(num + 1, num + n + 1);
    for(int i = 1; i <= n; i++)
        cout << num[i] << ' ';
    return 0;
}

这道题其实很简单，但是题目十分难懂。我们先看原题的描述：

人类终于登上了火星的土地并且见到了神秘的火星人。人类和火星人都无法理解对方的语言，但是我们的科学家发明了一种用数字交流的方法。这种交流方法是这样的，首先，火星人把一个非常大的数字告诉人类科学家，科学家破解这个数字的含义后，再把一个很小的数字加到这个大数上面，把结果告诉火星人，作为人类的回答。

火星人用一种非常简单的方式来表示数字――掰手指。火星人只有一只手，但这只手上有成千上万的手指，这些手指排成一列，分别编号为 ​1​,​2,​3​,​⋯​。火星人的任意两根手指都能随意交换位置，他们就是通过这方法计数的。

一个火星人用一个人类的手演示了如何用手指计数。如果把五根手指――拇指、食指、中指、无名指和小指分别编号为​1​,​2,3​,4和5，当它们按正常顺序排列时，形成了5位数12345，当你交换无名指和小指的位置时，会形成5位数12354​，当你把五个手指的顺序完全颠倒时，会形成 ​54321​，在所有能够形成的120个5位数中，12345 最小，它表示1​；12354第二小，它表示 ​2​；54321最大，它表示 ​120。

我来概括一下： 大意就是让你用next_permutation()对火星人的手指排列顺序进行更改，更改顺序为科学家给的那个小整数。

—————————————————————AC代码—————————————————————

#include <bits/stdc++.h>
using namespace std;
int n,a,num[10086];//定义变量和数组
int main(){
    cin>>n>>a;//输入火星人手指的个数和加上去的整数
    for (int i=1;i<=n;i++){
    cin>>num[i];//输入火星人手指的排列顺序
    }
    for(int i=1;i<=a;i++){
        next_permutation(num+1,num+n+1);//使用next_permutation()改变手指的排列顺序，循环a次
    }
    for(int i=1;i<=n;i++){
        cout<<num[i]<<" ";//依次输出
    }
    return 0;
}

编写题解不易，点个赞再把题解抱走吧！

哈！劳资来搞事情喽！代码+时间（本以为会超时，结果生生O（n + m）😕 ）

代码

下载

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int a[10005],m,n;
    cin >> n >> m;
    for (int i = 1;i <= n;i++) cin >> a[i];
    for (int i = 1;i <= m;i++) next_permutation(a + 1,a + n + 1);
    for (int i = 1;i <= n;i++) cout << a[i] << " ";
}

#include <iostream>
#include <algorithm>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n,m,a[10005];
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=m;i++)next_permutation(a+1,a+n+1);
    for(int i=1;i<=n;i++)cout<<a[i]<<' ';
    return 0;
}

因为是先变换，整体应该是whlle而不是do_while形式

P1017

题目回顾

对方的语言，但是我们的科学家发明了一种用数字交流的方法。这种交流方法是这样的，首先，火星人把一个非常大的数字告诉人类科学家，科学家破解这个数字的含义后，再把一个很小的数字加到这个大数上面，把结果告诉火星人，作为人类的回答。

火星人用一种非常简单的方式来表示数字――掰手指。火星人只有一只手，但这只手上有成千上万的手指，这些手指排成一列，分别编号为 ​1​,​2​,​3​,​⋯​。火星人的任意两根手指都能随意交换位置，他们就是通过这方法计数的。

一个火星人用一个人类的手演示了如何用手指计数。如果把五根手指――拇指、食指、中指、无名指和小指分别编号为​1​,​2​,​3​,4 和 ​5​，当它们按正常顺序排列时，形成了 5 位数 ​12345​，当你交换无名指和小指的位置时，会形成 5 位数 ​12354​，当你把五个手指的顺序完全颠倒时，会形成 ​54321​，在所有能够形成的120 个 5 位数中，12345 最小，它表示 ​1​；12354 第二小，它表示 ​2​；54321 最大，它表示 ​120​。

分析

这道题可以直接这样：

#include <bits/stdc++.h>
using namespace std;
int n,m,num[10005];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>num[i];
    }
    do
    {
        m--;
    }while(next_permutation(num+(n-6),num+n+1)&&m);
    for(int i=1;i<=n;i++){
        cout<<num[i]<<" ";
    }
    return 0;
}

其实也可以不这么复杂：

#include <bits/stdc++.h>
using namespace std;
int n,m,num[10005];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>num[i];
    }
    do
    {
        m--;
    }while(next_permutation(num+1,num+n+1)&&m);
    for(int i=1;i<=n;i++){
        cout<<num[i]<<" ";
    }
    return 0;
}

这样即可。

#include <iostream>
#include <algorithm>
using namespace std;
int num[10005];
int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        cin >> num[i];
    for (int i = 1; i <= m; ++i)
        next_permutation(num + 1, num + n + 1);
    for (int i = 1; i < n; ++i)
        cout << num[i] << ' ';
    cout << num[n];
}

#include <iostream>
#include <algorithm>
using namespace std;
int num[10005];
int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        cin >> num[i];
    for (int i = 1; i <= m; ++i)
        next_permutation(num + 1, num + n + 1);
    for (int i = 1; i < n; ++i)
        cout << num[i] << ' ';
    cout << num[n];
}

思路：

对于1~n的全排列，找到一个给定排列后的第m个排列。

对于当前序列重复执行m次next_permutation。

#include <iostream>
#include <algorithm>
using namespace std;
int num[10005];
int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)//输入n个整数的排列顺序
        cin >> num[i];
    //输入后对应num就像是题目中三进制数的最小值1，接下来如果m是5，那最后是加成6，对应外星人手指排列应该是321，输出321就行
    //123变到321是通过全排列5次得到，所以本题可以总结为以下：
    //对于当前序列重复执行m次next_permutation。
    for (int i = 1; i <= m; ++i)
        next_permutation(num + 1, num + n + 1);
    //输出第m次序列中的数
    for (int i = 1; i < n; ++i)
        cout << num[i] << ' ';
    cout << num[n];
}