题目描述
给定一个�(2≤�≤100000)位正整数�，将其划分成没有前导0的非空的两段，使这两段表示的正整数之和最小。数据保证至少有一个合法的划分。
解题思路
我们可以从中间开始向左边和向右边划分，分别找到左半部分得到的最小和和右半部分得到的最小和，然后比较它们的大小，输出较小的那个。
具体来说，我们可以用高精度加法来实现：
- 从左边开始找时，设左半部分为，右半部分为，初始时，为圆字符串的左半边再颠倒，为空字符串。每次将的最高位加到的最低位上，如果有进位，则将进位加到下一位上，同时从的最高位上删除已经加过的数字。如果此时或为空串或者带有前导0，则跳过此次循环。能找到的第一个情况就是从左边得到的最小和。
- 从右边开始找时，设左半部分为，右半部分为，初始时，为圆字符串的右半边再颠倒，为长度等于的长度的字符串。每次将的最高位加到的最低位上，如果有进位，则将进位加到下一位上，同时从的最高位上删除已经加过的数字。如果此时或为空串或者带有前导0，则跳过此次循环。能找到的第一个情况就是从右边得到的最小和。
最后比较左半部分得到的最小和和右半部分得到的最小和的大小，输出较小的那个即可。
代码实现
下面是用C++实现的代码，其中函数add()实现了高精度加法。
时间复杂度：
空间复杂度：
参考代码：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
const int mod = 998244353;
const int inf = 0x3f3f3f3f;
int main(){
string a, t, w, x, y;
int l;
scanf("%d", &l);
cin >> a;
int len = a.length();
reverse(a.begin(), a.end()); // 颠倒
for(int i = len/2; i >= 1; i--){
w = a.substr(0, i); // 圆字符串的左半边
t = ""; // 空字符串
if(w[w.length()-1] == '0' || t.empty()) continue; // 去除前导0和空串的情况
x = add(w, t); // 高精度加法
for(int i = 0; i < t.length(); i++){
x[i] += t[i] - '0';
if(x[i] > '9'){
x[i] -= 10;
x[i+1]++;
}
}
if(x[x.length()-1] > '0') x += '0'; // 进位
else x.erase(x.length()-1); // 去除前导0
break; // 能找到的第一个情况就是从左边得到的最小和
}
for(int i = (len+1)/2; i < len; i++){
t = a.substr(i, w.length()); // 圆字符串的右半边
w = ""; // 空字符串
if(w[w.length()-1] == '0' || t.empty()) continue; // 去除前导0和空串的情况
y = add(w, t); // 高精度加法
for(int i = 0; i < t.length(); i++){
y[i] += t[i] - '0';
if(y[i] > '9'){
y[i] -= 10;
y[i+1]++;
}
}
if(y[y.length()-1] > '0') y += '0'; // 进位
else y.erase(y.length()-1); // 去除前导0
break; // 能找到的第一个情况就是从右边得到的最小和
}
reverse(x.begin(), x.end()); // 变回个位在最后
reverse(y.begin(), y.end());
if(x.empty()) cout << y << endl;
else if(y.empty()) cout << x << endl;
else if(x.size() != y.size()){
cout << (x.size() < y.size() ? x : y);
return 0;
}
else{
for(int i = 0; i < x.size(); i++){
if(x[i] != y[i]){
cout << (x[i] < y[i] ? x : y);
return 0;
}
}
cout << x << " " << y << "\n";
}
return 0;
}
总结
本题主要考察了高精度加法和字符串操作，需要注意一些细节问题，如颠倒字符串、去除前导0、进位等。同时，还需要注意时间复杂度的控制，避免超时。
