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

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. 使用数字1-9（每个数字恰好用一次）组成三个三位数
2. 这三个三位数要满足比例 A:B:C
3. 按第一个数升序输出所有解，无解输出"No!!!"

解题思路

1. 暴力枚举法：使用1-9的所有排列（共9!种），对于每个排列：

   • 前3位组成第一个数，中间3位组成第二个数，后3位组成第三个数
   • 检查这三个数是否满足比例 A:B:C

2. 优化：

   • 利用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;}

功能分析

核心功能

1. 全排列生成：使用next_permutation生成数字1-9的所有排列
2. 数字组合：将每个排列分成三个三位数
3. 比例验证：验证三个数是否满足A:B:C的比例
4. 输出控制：按第一个数升序输出所有解（next_permutation本身按字典序生成排列）

时间与空间复杂度

• 时间复杂度：O(9! * O(1)) ≈ O(362880)，可以接受
• 空间复杂度：O(9)，只存储1-9的排列

算法特点

1. 简洁性：利用STL的next_permutation简化了全排列生成
2. 正确性：枚举所有可能组合，不会漏解
3. 高效性：用整数乘法避免浮点数精度问题

完整系列资料，请查看专栏：《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;}