企业官网建设流程全解析

【题目来源】

学而思编程：最小结果

【题目描述】

给定一个字符串s t r strstr，保证字符串由a ( a > 1 ) a(a>1)a(a>1)个数字字符和1 11个字符’+'组成。

现在你可以向字符串s t r strstr中添加一对括号：

1. 左括号必须添加在’+'的左侧；
2. 右括号必须添加在’+'的右侧；

假设左括号左边的数字从左到右组成的整数为p pp，左括号与’+‘之间的数字从左到右组成的整数为q qq，’+'与右括号之间的数字从左到右组成的整数为r rr，右括号右边的数字从左到右组成的整数为s ss。

请你安排左括号和右括号的位置，使得p ∗ ( q + r ) ∗ s p * (q + r) * sp∗(q+r)∗s最小，并输出这个最小值。

注意，如果左括号在字符串最左侧，认为p = 1 p=1p=1，类似的，如果右括号在字符串最右侧，认为s = 1 s=1s=1，则’+'两边必须存在数字。

【输入】

一行一个字符串s t r strstr，保证’+'的位置合法。

【输出】

一行一个整数，表示p ∗ ( q + r ) ∗ s p * (q + r) * sp∗(q+r)∗s的最小值。

【输入样例】

12+34

【输出样例】

20

【核心思想】

1. 问题分析：给定由数字和单个+组成的字符串，在+左右两侧各选一个位置插入括号，将字符串分割为四部分p , q , r , s p, q, r, sp,q,r,s，使得p × ( q + r ) × s p \times (q + r) \times sp×(q+r)×s最小。其中p pp和s ss可以为空（此时值为1 11），q qq和r rr必须非空。这是一个枚举 + 字符串解析问题，核心在于确定分割点的合法范围并遍历所有可能。

2. 算法选择：

   • 枚举分割点：左括号位置i ii在+左侧遍历，右括号位置j jj在+右侧遍历，枚举所有O ( n 2 ) O(n^2)O(n2)种分割方案
   • 字符串转整数：利用substr和stoi将子串解析为整数，处理前导零和边界情况

3. 关键步骤：

   • 定位加号：找到+在字符串中的位置m i d midmid
   • 枚举左括号位置（i ii从0 00到m i d − 1 mid-1mid−1）：
     • p pp：s [ 0.. i − 1 ] s[0..i-1]s[0..i−1]组成的整数，若i = 0 i=0i=0则p = 1 p=1p=1
     • q qq：s [ i . . m i d − 1 ] s[i..mid-1]s[i..mid−1]组成的整数
   • 枚举右括号位置（j jj从m i d + 1 mid+1mid+1到n − 1 n-1n−1）：
     • r rr：s [ m i d + 1.. j ] s[mid+1..j]s[mid+1..j]组成的整数
     • s ss：s [ j + 1.. n − 1 ] s[j+1..n-1]s[j+1..n−1]组成的整数，若j = n − 1 j=n-1j=n−1则s = 1 s=1s=1
   • 计算并更新最小值：r e s u l t = p × ( q + r ) × s result = p \times (q + r) \times sresult=p×(q+r)×s，维护全局最小值b e s t bestbest
   • 输出结果：b e s t bestbest

4. 时间/空间复杂度：

   • 时间复杂度：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)，仅使用常数额外空间

5. 枚举与字符串解析的核心思想：

   • 合法分割点约束：左括号必须在+左侧（i ∈ [ 0 , m i d − 1 ] i \in [0, mid-1]i∈[0,mid−1]），右括号必须在+右侧（j ∈ [ m i d + 1 , n − 1 ] j \in [mid+1, n-1]j∈[mid+1,n−1]），q qq和r rr必须包含至少一个数字字符
   • 边界值处理：当左括号在最左侧（i = 0 i=0i=0）时p = 1 p=1p=1，右括号在最右侧（j = n − 1 j=n-1j=n−1）时s = 1 s=1s=1，通过条件判断避免空串转整数的错误
   • 全枚举保证最优：由于分割点数量有限（最多O ( n 2 ) O(n^2)O(n2)种），直接枚举所有合法方案即可找到全局最小值，无需复杂优化
   • 子串解析技巧：利用substr(pos, len)配合stoi将字符串片段转为整数，注意长度计算为mid - i和j - mid等
   • 适用于字符串分割、括号插入位置枚举类问题，特别是搜索空间较小、可以直接暴力枚举的场景

【算法标签】

#字符串入门

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;intmain(){string s;cin>>s;// 输入表达式字符串intn=s.size();// 字符串长度intmid=s.find('+');// 找到加号的位置intbest=2e9;// 初始化为一个大数// 遍历所有可能的分割方式for(inti=0;i<mid;i++)// 第一个分割点（乘号）在加号左边{for(intj=mid+1;j<n;j++)// 第二个分割点（乘号）在加号右边{// 解析四个数字inta=(i==0?1:stoi(s.substr(0,i)));// 第一个乘数intb=stoi(s.substr(i,mid-i));// 加号左边的第二个乘数intc=stoi(s.substr(mid+1,j-mid));// 加号右边的第一个乘数intd=(j==n-1?1:stoi(s.substr(j+1,n-j-1)));// 最后一个乘数// 计算表达式结果：a * (b + c) * dintresult=a*(b+c)*d;// 更新最小值if(result<=best)best=result;}}cout<<best;// 输出最小值return0;}

【运行结果】

12+34 20