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

【题目来源】学而思编程最小结果【题目描述】给定一个字符串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