Codeforces Round #567 (Div. 2) B. Split a Number

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int amn=1e5+5;
 4 char in[amn],n1[amn],n2[amn];
 5 int l,tp;
 6 struct bignum{                  ///大数加法的模板
 7     int len,n[amn];
 8     void getnum(char in[]){
 9         len=strlen(in);
10         for(int i=0;i<len;i++){
11             n[i]=in[len-i-1]-'0';
12         }
13     }
14     void add(bignum a,bignum b){
15         int le=max(a.len,b.len);
16         int x,c=0;
17         len=0;
18         for(int i=0;i<le||c;i++){
19             x=c;
20             if(i<a.len)x+=a.n[i];
21             if(i<b.len)x+=b.n[i];
22             c=x/10;
23             x%=10;
24             n[i]=x;
25             len++;
26         }
27     }
28     int big(bignum a,bignum b){ ///比较大小
29         if(a.len>b.len)return 1;
30         if(a.len<b.len)return -1;
31         for(int i=a.len-1;i>=0;i--){
32             if(a.n[i]>b.n[i])return 1;
33             if(a.n[i]<b.n[i])return -1;
34         }
35         return 0;
36     }
37     void out(){
38         for(int i=len-1;i>=0;i--){
39             printf("%c",n[i]+'0');
40         }
41         printf("\n");
42     }
43 }a,b,c,d;
44 int fd(int x,int d){
45     int lx=x;
46     if(d)         ///看现在要向左扩展还是向右扩展
47         while(in[x]=='0'&&x>=0)x--; ///因为一个数的开头不能有前导0（单个0不算前导0）如果mid那一位为0，向左扩展mid
48     else
49         while(in[x]=='0'&&x<l)x++;  ///如果mid那一位为0，向右扩展mid
50     if((x==l/2)&&l%2){          ///如果中间没有前导0且长度为基数，则会产生左右数长度不等的情况，所以要看mid这个数给左边能使他们两个之和更小还是给右边能使他们两个之和更小
51         for(int i=0;i<=x;i++){  ///现在默认mid放右边的数
52             if(in[i]<in[i+x]){  ///从最高位依次判断两个数的大小如果左边的比右边的更小则把中间这个数给左边，使左边增加一位，右边减少一位，这样两个数之和是更小的，因为，左边那一位小于右边那一位了，左边增加的肯定是小于右边减少的，故能使整体之和更小，举个例子，123中间是2，现在默认给右边的，分开来就是1,23，现在来判断，1<2，则把中间那个给左边的数，变成12,3，现在发现，左边增加了11，右边减少了20，所以左边增加的小于右边减少的，那么总体是减少的
53                 if(in[x+1]!='0')///mid右边不能为0才能右移因为，不然就有前导0了
54                 x++;
55                 break;
56             }
57             else if(in[i]>in[i+x]) break;   ///如果左边的数大于右边的数，那么把中间这个数放右边是更优的
58         }
59     }
60     return x;
61 }
62 int main(){
63     ios::sync_with_stdio(0);
64     cin>>l>>in;             ///怎样分才能让两个数之和最大？贪心地想是从中间开始分，但要考虑中间为0和长度为基数的情况，所以就要考虑是左边的数更长一点好还是右边的数更长一点好
65     int mid=fd(l/2,0);     ///优先把mid选在右边
66     for(int i=0;i<mid;i++)
67         n1[i]=in[i];
68     tp=0;
69     for(int i=mid;i<l;i++)
70         n2[tp++]=in[i];
71     a.getnum(n1),b.getnum(n2);
72     c.add(a,b);             ///大数加法，下面同理
73     mid=fd(l/2,1);         ///优先把mid选在左边
74     memset(n1,0,sizeof n1);   ///因为2次mid可能算的不一样，所以n1,n2记得要清0，不然可能会保留上一次的东西
75     memset(n2,0,sizeof n2);
76     for(int i=0;i<mid;i++)
77         n1[i]=in[i];
78     tp=0;
79     for(int i=mid;i<l;i++)
80         n2[tp++]=in[i];
81     a.getnum(n1),b.getnum(n2);
82     d.add(a,b);
83     if(a.big(c,d)<0)       ///选一个小的输出
84         c.out();
85     else
86         d.out();
87 }
88 /***
89 有一个数n，长度为l，l是n的位数有多少个，注意l最多有1e5（这是什么一个概念，long long 最多有18位，一开始我理解错题意了，就用long long写了）
90 要求将这个数n分割为2个没有前导0的正整数使得这2个正整数和最小
91 注意到l最大有1e5，爆long long了，就祭出大数加法模板，现在就考虑怎么分的问题
92 怎样分才能让两个数之和最大？贪心地想是从中间开始分，但要考虑中间为0和长度为基数的情况，所以就要考虑是左边的数更长一点好还是右边的数更长一点好
93 先优先把mid选在右边，因为一个数的开头不能有前导0（单个0不算前导0），如果mid那一位为0，向右扩展mid，如果中间没有前导0且长度为基数，则会产生左右数长度不等的情况，所以要看mid这个数给左边能使他们两个之和更小还是给右边能使他们两个之和更小
94 现在默认mid放右边的数，从最高位依次判断两个数的大小如果左边的比右边的更小则把中间这个数给左边，使左边增加一位，右边减少一位，这样两个数之和是更小的，因为，左边那一位小于右边那一位了，左边增加的肯定是小于右边减少的，故能使整体之和更小，举个例子，123中间是2，现在默认给右边的，分开来就是1,23，现在来判断，1<2，则把中间那个给左边的数，变成12,3，现在发现，左边增加了11，右边减少了20，所以左边增加的小于右边减少的，那么总体是减少的
95 注意mid右边不能为0才能右移因为，不然就有前导0了，而如果左边的数大于右边的数，那么把中间这个数放右边是更优的
96 接下来优先把mid放左边，与上面同理，注意因为2次mid可能算的不一样，所以n1,n2记得要清0，不然可能会保留上一次的东西，一开始因为没清零WA了几次
97 最后判断是mid放左边更小还是mid放右边更小，选一个小的输出
98 ***/