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） - 每个排列的下一个排列是字典序稍大的排列，前一个排列是字典序稍小的排列
解决这个问题有两种常见方法：
- 使用标准库函数：C++ STL 提供了
prev_permutation函数，可以直接求前一个排列 - 手动实现算法：通过寻找"转折点"并交换元素
代码实现
#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;}功能分析
核心功能
- 输入处理：读取排列长度N和具体的排列序列
- 前一个排列计算：使用
prev_permutation算法 - 边界处理：当排列已是第一个时输出"ERROR"
prev_permutation工作原理
该函数的内部算法步骤如下：
- 从序列末尾向前查找第一个逆序的位置i（即
a[i] > a[i+1]） - 如果找不到这样的i，说明序列是升序的（第一个排列），返回false
- 从序列末尾向前查找第一个小于
a[i]的元素a[j] - 交换
a[i]和a[j] - 将
i+1到末尾的元素反转（变为降序） - 返回true
复杂度分析
- 时间复杂度：O(N)，
prev_permutation最多遍历序列两次 - 空间复杂度：O(N)，存储排列需要N个整数的空间
示例验证
以输入3\n1 3 2为例：
- 初始排列：
[1, 3, 2] prev_permutation找到：- 逆序点：索引0（值1），因为1<3，继续；索引1（值3），因为3>2，找到i=1
- 从末尾找小于3的值：索引2（值2）
- 交换3和2：得到
[1, 2, 3] - 反转i+1后的序列：不变
- 输出：
1 2 3
边界情况
- 最小情况：N=1，只有一个排列，前一个排列不存在，输出"ERROR"
- 第一个排列：如输入
1 2 3，输出"ERROR" - 最后一个排列：如输入
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;}
