主要思想
很明显,题面就是让你将一串数割开,使得隔开后的两数总和最小。
稍微分析一下后我们会想到:对于这里隔开后的两个数,他们的总位数一定,显然他们的位数越相近,总和就有机会越小。所以我们尝试从这串数的正中央着手割开,使用高精度进行操作。
我们从这串数的最中央开始分割,先尝试向左移动,找到该过程中第一个符合题意要求的方案,记录结果。然后再尝试向右移动,再找到该过程中第一个符合题意要求的方案,记录下来。最后比较两结果,取较小者。
本文中使用双端队列模拟高精度,使用较为便利。
代码
#pragma GCC optimize ("O2") #pragma G++ optimize ("O2") #include <bits/stdc++.h> using namespace std; #define QUICK #ifdef QUICK #define R register #else #define R #endif //定义输出deque高精度的方法 ostream& operator << (ostream &out,deque<int>& x) { for (R deque<int>::iterator it=x.begin();it!=x.end();it++) { out<<char(*it+'0'); } out<<std::endl; return out; }; int main() { #ifdef QUICK ios::sync_with_stdio(false);//流加速 #endif deque<int> a,b,s,c,d,n; //a,b存放第一次割法的前后者情况 //c,d存放第二次割法的前后者情况 //s,n分别存放两次割法的和 int l; cin>>l; for (R int point=1;point<=l;point++) { char t; cin>>t; if(point<=l/2) { a.push_back(t-'0'); c.push_back(t-'0'); }//前半段数 else { b.push_back(t-'0'); d.push_back(t-'0'); }//后半段数 } a.push_back(b.front()); b.pop_front(); a.push_back(b.front()); b.pop_front(); d.push_front(c.back()); c.pop_back(); //向左搜索 while(!a.empty()) { b.push_front(a.back()); a.pop_back(); if(a.empty()||b.empty()||a.front()==0||b.front()==0) {//判断为空或是前缀0 continue; } deque<int>::reverse_iterator pa=a.rbegin(),pb=b.rbegin(); //反向迭代器 int g=0; //相加 for(;pa!=a.rend()&&pb!=b.rend();++pa,++pb) { s.push_front((*pa+*pb+g)%10); g=(*pa+*pb+g)/10; } while(pa!=a.rend()) { s.push_front((*pa+g)%10); g=(*pa+g)/10; pa++; } while(pb!=b.rend()) { s.push_front((*pb+g)%10); g=(*pb+g)/10; pb++; } if(g!=0) { s.push_front(g); } break; } //向右搜索 while(!d.empty()) { c.push_back(d.front()); d.pop_front(); if(c.empty()||d.empty()||c.front()==0||d.front()==0) { continue; } deque<int>::reverse_iterator pc=c.rbegin(),pd=d.rbegin(); int g=0; for(;pc!=c.rend()&&pd!=d.rend();++pc,++pd) { n.push_front((*pc+*pd+g)%10); g=(*pc+*pd+g)/10; } while(pc!=c.rend()) { n.push_front((*pc+g)%10); g=(*pc+g)/10; pc++; } while(pd!=d.rend()) { n.push_front((*pd+g)%10); g=(*pd+g)/10; pd++; } if(g!=0) { n.push_front(g); } break; } // cout<<a<<b<<c<<d<<s<<n; //判断s与n的大小,取小者输出 if(s.size()==0) { cout<<n<<std::endl; return 0; } if(n.size()==0) { cout<<s<<std::endl; return 0; } if(s.size()!=n.size()) { if(s.size()<n.size()) { cout<<s<<std::endl; } else { cout<<n<<std::endl; } return 0; } else {//逐位判断 deque<int>::iterator ps=s.begin(),pn=n.begin(); for(;ps!=s.end()&&pn!=n.end();ps++,pn++) { if(*pn!=*ps) { if(*ps<*pn) { cout<<s<<std::endl; } else { cout<<n<<std::endl; } return 0; } } } cout<<n<<std::endl; return 0; }
Comments | NOTHING