洛谷:P1088:火星人


洛谷:P1088:火星人

Table of Contents

题目

P1088:火星人

分析

这道题目听起来很绕。但要注意到其中的描述:

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

如果对上述的描述感觉“熟悉”,同时我们对比较小的数字的阶乘比较熟悉的话,就会想到:\(P_5^5=120\),也就是5个元素选择5个元素的全排列数量。

于是,我们要想到C++中的内置全排列函数next_permutation,它可以根据当前的排列状态,生成下一个全排列。

next_permutation(fingers + 1, fingers + n + 1);

该函数的两个参数含义是一个左闭右开的区间。这里从fingers+1开始(因为我们用了1-基数组),到fingers_n结束(因为右边是开区间)。根据输入的m,循环求下一个即可。

答案

Solution

思考

这道题不难。掌握了内置函数next_permutation就可以。一些讨论,可以参见这个帖子

上一篇 下一篇