csp信奥赛C++标准模板库STL案例应用24

csp信奥赛C++标准模板库STL案例应用24

prev_permutation实践

题目描述

情人节到了，Uim打算给他的后宫们准备情人节礼物。UIm 一共有N NN（1 ≤ N ≤ 9 1\le N\le 91≤N≤9）个后宫妹子（现充去死挫骨扬灰!）。

为了维护他的后宫的稳定。他通过编程，得出了一个送礼物的最佳顺序。这个我们管不着。

然而他认为，如果什么事情做得太圆满不是什么好事。于是他希望得到原定顺序的前一个字典序的序列。

输入格式

第一行一个整数N NN。

第二行N NN个整数，表示原定排列。

输出格式

输出N NN个数，表示给定排列的前一个排列。特别地，若当前排列已经是第一个，则输出ERROR。

输入输出样例 1

输入 1

3 1 3 2

输出 1

1 2 3

思路分析

这道题的核心是求给定排列的前一个字典序排列。字典序排列的顺序定义如下：

• 第一个排列是升序排列（如1 2 3 ... N）
• 最后一个排列是降序排列（如N ... 3 2 1）
• 每个排列的下一个排列是字典序稍大的排列，前一个排列是字典序稍小的排列

解决这个问题有两种常见方法：

1. 使用标准库函数：C++ STL 提供了prev_permutation函数，可以直接求前一个排列
2. 手动实现算法：通过寻找"转折点"并交换元素

代码实现

#include<bits/stdc++.h>// 包含所有标准库头文件（竞赛常用写法）usingnamespacestd;intn,x;// n: 排列长度，x: 临时变量用于读取输入intmain(){// 读取排列长度cin>>n;// 使用vector存储排列vector<int>a;// 读取原始排列for(inti=1;i<=n;i++){cin>>x;a.push_back(x);// 将每个数字添加到vector末尾}// 使用STL的prev_permutation求前一个排列// 函数功能：// 1. 如果存在前一个字典序排列，将a变为该排列并返回true// 2. 如果当前排列是第一个排列（升序），返回false且不修改aif(prev_permutation(a.begin(),a.end())){// 存在前一个排列，输出结果for(inti=0;i<n;i++){cout<<a[i]<<" ";}}else{// 当前排列已是第一个排列，输出ERRORcout<<"ERROR";}return0;}

功能分析

核心功能

1. 输入处理：读取排列长度N和具体的排列序列
2. 前一个排列计算：使用prev_permutation算法
3. 边界处理：当排列已是第一个时输出"ERROR"

prev_permutation工作原理

该函数的内部算法步骤如下：

1. 从序列末尾向前查找第一个逆序的位置i（即a[i] > a[i+1]）
2. 如果找不到这样的i，说明序列是升序的（第一个排列），返回false
3. 从序列末尾向前查找第一个小于a[i]的元素a[j]
4. 交换a[i]和a[j]
5. 将i+1到末尾的元素反转（变为降序）
6. 返回true

复杂度分析

• 时间复杂度：O(N)，prev_permutation最多遍历序列两次
• 空间复杂度：O(N)，存储排列需要N个整数的空间

示例验证

以输入3\n1 3 2为例：

1. 初始排列：[1, 3, 2]
2. prev_permutation找到：
   • 逆序点：索引0（值1），因为1<3，继续；索引1（值3），因为3>2，找到i=1
   • 从末尾找小于3的值：索引2（值2）
   • 交换3和2：得到[1, 2, 3]
   • 反转i+1后的序列：不变
3. 输出：1 2 3

边界情况

1. 最小情况：N=1，只有一个排列，前一个排列不存在，输出"ERROR"
2. 第一个排列：如输入1 2 3，输出"ERROR"
3. 最后一个排列：如输入3 2 1，前一个排列是3 1 2

---

完整系列资料，请查看专栏：《csp信奥赛C++标准模板库STL》

https://blog.csdn.net/weixin_66461496/category_13108077.html

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}

• 一、CSP信奥赛C++通关学习视频课：
  • C++语法基础
  • C++语法进阶
  • C++算法
  • C++数据结构
  • CSP信奥赛数学
  • CSP信奥赛STL
• 二、CSP信奥赛C++竞赛拿奖视频课：
  • 信奥赛csp-j初赛高频考点解析
  • CSP信奥赛C++复赛集训课（12大高频考点专题集训）
• 三、考级、竞赛刷题题单及题解：
  • GESP C++考级真题题解
  • CSP信奥赛C++初赛及复赛高频考点真题解析
  • CSP信奥赛C++一等奖通关刷题题单及题解

---

详细内容：

1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：

https://edu.csdn.net/lecturer/7901 点击跳转

2、CSP信奥赛C++竞赛拿奖视频课：

https://edu.csdn.net/course/detail/40437 点击跳转

3、csp信奥赛冲刺一等奖有效刷题题解：

CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

• 2025 csp-j 复赛真题及答案解析（最新更新）
• 2025 csp-x(山东) 复赛真题及答案解析（最新更新）
• 2025 csp-x(河南) 复赛真题及答案解析（最新更新）
• 2025 csp-x(辽宁) 复赛真题及答案解析（最新更新）
• 2025 csp-x(江西) 复赛真题及答案解析（最新更新）
• 2025 csp-x(广西) 复赛真题及答案解析（最新更新）
• 2020 ~ 2024 csp 复赛真题题单及题解
• 2019 ~ 2022 csp-j 初赛高频考点真题分类解析
• 2021 ~ 2024 csp-s 初赛高频考点解析
• 2023 ~ 2024 csp-x (山东)初赛真题及答案解析
• 2024 csp-j 初赛真题及答案解析
• 2025 csp-j 初赛真题及答案解析（最新更新）
• 2025 csp-s 初赛真题及答案解析（最新更新）
• 2025 csp-x (山东)初赛真题及答案解析(最新更新)
• 2025 csp-x (江西)初赛真题及答案解析(最新更新)
• 2025 csp-x (辽宁)初赛真题及答案解析(最新更新)

CSP信奥赛C++一等奖通关刷题题单及题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转

• 129 道刷题练习和详细题解，涉及：模拟算法、数学思维、二分算法、 前缀和、差分、深搜、广搜、DP专题、 树和图

4、GESP C++考级真题题解：

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}