题目链接: https://www.luogu.org/problem/CF1181B
题意: 给你一个 l(2<=l<=100000) 位正整数 n, 将其划分成没有前导 0 的非空的两段, 使这两段表示的正整数之和最小. 数据保证至少有一个合法的划分.
分析: 我们知道, 模拟高精度加法的时间复杂度是 O(N), 暴力枚举切割位置那就是 O(N^2) 的, 肯定 T, 很容易想到从中间开始切割.
我们直接分别从中间开始向左边和向右边划分, 两边能找到的第一个情况就是最小情况 (因为此时两部分位数相差最小)
思想很简单, 高精度加法仔细看看, 像为什么要颠倒, 进位如何做到的都给看看.
为了方便理解, 画个图
图示便是从左边开始找时 w,t 的初始位置 (注意下标方向)
- #include <bits/stdc++.h>
- using namespace std;
- const int maxn=1e5+7;
- const long long mod=998244353;
- const int inf=1<<30;
- typedef long long ll;
- #define meminf(a) memset(a,0x3f,sizeof(a))
- #define mem0(a) memset(a,0,sizeof(a));
- string a,t,w,x,y;
- //x,y 分别是左半边得到的最小和以及从右半边得到的最小和
- int main(){
- int l;scanf("%d",&l);
- cin>>a;
- int len=a.length();
- reverse(a.begin(),a.end());
- // 这里颠倒是因为高精度加法需要从后往前加的
- for(int i=len/2;i>=0;i--){
- x="";
- t=a.substr(0,i);
- w=a.substr(i,len-i);
- // 此时 w 其实是圆字符串的左半边再颠倒
- //w 的长度是一定大于等于 t 的长度的
- if(w[w.length()-1]=='0'||t[t.length()-1]=='0'||w.empty()||t.empty()) continue;
- // 去除前导 0 和空串的情况
- x=w;
- // 高精度加法
- for(int i=0;i<t.length();i++){
- x[i]+=t[i]-'0';
- }
- for(int i=0;i<w.length()-1;i++){
- while(x[i]>'9') x[i]-=10,x[i+1]++;
- }
- if(x[x.length()-1]>'9') x[x.length()-1]-=10,x+='1';
- break;// 能找到的第一个情况就是从左边得到的最小和
- }
- for(int i=(len+1)/2;i<len;i++){
- y="";
- w=a.substr(0,i);
- t=a.substr(i,len-i);
- //w 的长度是一定大于等于 t 的长度的, 注意和上一个相比, w,t 互换位置了
- if(w[w.length()-1]=='0'||t[t.length()-1]=='0'||w.empty()||t.empty()) continue;
- // 去除前导 0 和空串的情况
- y=w;
- for(int i=0;i<t.length();i++){
- y[i]+=t[i]-'0';
- }
- for(int i=0;i<w.length()-1;i++){
- if(y[i]>'9') y[i]-=10,y[i+1]++;
- }
- if(y[y.length()-1]>'9') y[y.length()-1]-=10,y+='1';
- break;// 能找到的第一个情况就是从右边得到的最小和
- }
- reverse(x.begin(),x.end());
- reverse(y.begin(),y.end());
- //x,y 此时都是个位在最前, 变回个位在最后
- 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";
- cout<<x;
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3166574.html