csp信奥赛C++标准模板库STL案例应用23
next_permutation实践
题目描述
将1 , 2 , … , 9 1, 2,\ldots, 91,2,…,9共9 99个数分成三组，分别组成三个三位数，且使这三个三位数的比例是A : B : C A:B:CA:B:C，试求出所有满足条件的三个三位数，若无解，输出No!!!。
//感谢黄小U饮品完善题意
输入格式
三个数，A , B , C A,B,CA,B,C。
输出格式
若干行，每行3 33个数字。按照每行第一个数字升序排列。
输入输出样例 1
输入 1
1 2 3输出 1
192 384 576 219 438 657 273 546 819 327 654 981说明/提示
保证0 ≤ A < B < C ≤ 999 0 \le A<B<C \le 9990≤A<B<C≤999。
思路分析
这个问题是一个数字组合问题，要求：
- 使用数字1-9（每个数字恰好用一次）组成三个三位数
- 这三个三位数要满足比例 A:B:C
- 按第一个数升序输出所有解，无解输出"No!!!"
解题思路
暴力枚举法：使用1-9的所有排列（共9!种），对于每个排列：
- 前3位组成第一个数，中间3位组成第二个数，后3位组成第三个数
- 检查这三个数是否满足比例 A:B:C
优化：
- 利用
next_permutation生成全排列，自动按字典序排列 - 用乘法验证比例：
n1*b == n2*a && n1*c == n3*a
- 利用
代码实现
#include<bits/stdc++.h>usingnamespacestd;inta,b,c;// 输入的比例系数A,B,Cintmain(){// 读入比例系数cin>>a>>b>>c;// 初始化数组，包含1-9这9个数字vector<int>v;for(inti=1;i<=9;i++){v.push_back(i);}boolf=false;// 标记是否有解// 使用next_permutation生成1-9的所有全排列do{// 将排列分成三个三位数intn1=v[0]*100+v[1]*10+v[2];// 前3位组成第一个数intn2=v[3]*100+v[4]*10+v[5];// 中间3位组成第二个数intn3=v[6]*100+v[7]*10+v[8];// 后3位组成第三个数// 检查比例关系（避免浮点误差，用乘法比较）// 条件等价于：n1/n2 = a/b 且 n1/n3 = a/cif(n1*b==n2*a&&n1*c==n3*a){cout<<n1<<" "<<n2<<" "<<n3<<endl;f=true;// 找到至少一个解}}while(next_permutation(v.begin(),v.end()));// 生成下一个排列// 如果没有找到任何解if(!f){cout<<"No!!!";}return0;}功能分析
核心功能
- 全排列生成：使用
next_permutation生成数字1-9的所有排列 - 数字组合：将每个排列分成三个三位数
- 比例验证：验证三个数是否满足A:B:C的比例
- 输出控制：按第一个数升序输出所有解（
next_permutation本身按字典序生成排列）
时间与空间复杂度
- 时间复杂度：O(9! * O(1)) ≈ O(362880)，可以接受
- 空间复杂度：O(9)，只存储1-9的排列
算法特点
- 简洁性：利用STL的
next_permutation简化了全排列生成 - 正确性：枚举所有可能组合，不会漏解
- 高效性：用整数乘法避免浮点数精度问题
完整系列资料，请查看专栏：《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;}
