题解：学而思编程最小结果-北京尧图网络

【题目来源】学而思编程最小结果【题目描述】给定一个字符串s t r strstr保证字符串由a ( a 1 ) a(a1)a(a1)个数字字符和1 11个字符’组成。现在你可以向字符串s t r strstr中添加一对括号左括号必须添加在’的左侧右括号必须添加在’的右侧假设左括号左边的数字从左到右组成的整数为p pp左括号与’‘之间的数字从左到右组成的整数为q qq’与右括号之间的数字从左到右组成的整数为r rr右括号右边的数字从左到右组成的整数为s ss。请你安排左括号和右括号的位置使得p ∗ ( q r ) ∗ s p * (q r) * sp∗(qr)∗s最小并输出这个最小值。注意如果左括号在字符串最左侧认为p 1 p1p1类似的如果右括号在字符串最右侧认为s 1 s1s1则’两边必须存在数字。【输入】一行一个字符串s t r strstr保证’的位置合法。【输出】一行一个整数表示p ∗ ( q r ) ∗ s p * (q r) * sp∗(qr)∗s的最小值。【输入样例】1234【输出样例】20【核心思想】问题分析给定由数字和单个组成的字符串在左右两侧各选一个位置插入括号将字符串分割为四部分p , q , r , s p, q, r, sp,q,r,s使得p × ( q r ) × s p \times (q r) \times sp×(qr)×s最小。其中p pp和s ss可以为空此时值为1 11q qq和r rr必须非空。这是一个枚举字符串解析问题核心在于确定分割点的合法范围并遍历所有可能。算法选择枚举分割点左括号位置i ii在左侧遍历右括号位置j jj在右侧遍历枚举所有O ( n 2 ) O(n^2)O(n2)种分割方案字符串转整数利用substr和stoi将子串解析为整数处理前导零和边界情况关键步骤定位加号找到在字符串中的位置m i d midmid枚举左括号位置i ii从0 00到m i d − 1 mid-1mid−1p pps [ 0.. i − 1 ] s[0..i-1]s[0..i−1]组成的整数若i 0 i0i0则p 1 p1p1q qqs [ i . . m i d − 1 ] s[i..mid-1]s[i..mid−1]组成的整数枚举右括号位置j jj从m i d 1 mid1mid1到n − 1 n-1n−1r rrs [ m i d 1.. j ] s[mid1..j]s[mid1..j]组成的整数s sss [ j 1.. n − 1 ] s[j1..n-1]s[j1..n−1]组成的整数若j n − 1 jn-1jn−1则s 1 s1s1计算并更新最小值r e s u l t p × ( q r ) × s result p \times (q r) \times sresultp×(qr)×s维护全局最小值b e s t bestbest输出结果b e s t bestbest时间/空间复杂度时间复杂度O ( n 2 ⋅ L ) O(n^2 \cdot L)O(n2⋅L)其中n nn为字符串长度L LL为数字位数stoi的复杂度由于数字字符总数固定且较少实际为O ( n 2 ) O(n^2)O(n2)空间复杂度O ( 1 ) O(1)O(1)仅使用常数额外空间枚举与字符串解析的核心思想合法分割点约束左括号必须在左侧i ∈ [ 0 , m i d − 1 ] i \in [0, mid-1]i∈[0,mid−1]右括号必须在右侧j ∈ [ m i d 1 , n − 1 ] j \in [mid1, n-1]j∈[mid1,n−1]q qq和r rr必须包含至少一个数字字符边界值处理当左括号在最左侧i 0 i0i0时p 1 p1p1右括号在最右侧j n − 1 jn-1jn−1时s 1 s1s1通过条件判断避免空串转整数的错误全枚举保证最优由于分割点数量有限最多O ( n 2 ) O(n^2)O(n2)种直接枚举所有合法方案即可找到全局最小值无需复杂优化子串解析技巧利用substr(pos, len)配合stoi将字符串片段转为整数注意长度计算为mid - i和j - mid等适用于字符串分割、括号插入位置枚举类问题特别是搜索空间较小、可以直接暴力枚举的场景【算法标签】#字符串入门【代码详解】#includebits/stdc.husingnamespacestd;intmain(){string s;cins;// 输入表达式字符串intns.size();// 字符串长度intmids.find();// 找到加号的位置intbest2e9;// 初始化为一个大数// 遍历所有可能的分割方式for(inti0;imid;i)// 第一个分割点乘号在加号左边{for(intjmid1;jn;j)// 第二个分割点乘号在加号右边{// 解析四个数字inta(i0?1:stoi(s.substr(0,i)));// 第一个乘数intbstoi(s.substr(i,mid-i));// 加号左边的第二个乘数intcstoi(s.substr(mid1,j-mid));// 加号右边的第一个乘数intd(jn-1?1:stoi(s.substr(j1,n-j-1)));// 最后一个乘数// 计算表达式结果a * (b c) * dintresulta*(bc)*d;// 更新最小值if(resultbest)bestresult;}}coutbest;// 输出最小值return0;}【运行结果】1234 20

题解：学而思编程最小结果

相关推荐

3步搞定Sunshine游戏串流：小白也能上手的私人云游戏平台搭建指南

实战复现CitrixBleed 2漏洞：从内存越界读取到会话劫持

免费开源鼠标连点器完整指南：告别重复点击的终极解决方案

更多资讯

ZLM WebRTC播放配置避坑与QoS调优实战

DeepSeekMoE：混合专家模型的专业化突破与实践

BIP39 助记词生成原理：从熵、校验和到 2048 词表索引映射

AI智能体开发：系统化学习路线与核心技术栈解析

SketchUp参数化坯子插件库：建筑构件的工程化建模中枢

从词法分析到三地址码：小型编译器的链路与避坑

今日更新

学生选课系统DFD图绘制指南：边界划分与分层校验实战

JIRA敏捷落地：Scrum角色权限、Sprint与燃尽图避坑指南

SEMI S8人机工程验收实战：从条款拆解到现场实测的完整指南

本周精选

防幻觉智能体架构：电源硬件设计中的大模型编排与工具化实践

OpenGL面试核心考点：渲染管线、矩阵变换与性能排查全解析

全国计算机二级C语言真题PDF高效刷题指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？