给你一个 n_s,拆成 a+b=n_s,把 a 和 b 的数字连起来得到新数,找所有拆法中这个新数的最大值。
思路
1.设 a+b=n,b 是 k 位数,则拼接结果:C = a \times 10^k + b,因为 C = (n - b) \times 10^k + b。
2.当 b 的位数固定为 k 时,k 就固定了,10^k是常数。对 b 求导:\frac{dC}{db} = -10^k + 1,因为 k \ge 1,所以 -10^k+1,C 随着 b 增大而减小。因此,对于固定位数 k,要最大化 C,必须取最小的可能的 k 位数作为 b。最小的 k 位数是 10^{k-1}。
算法步骤
读入 n。对于 k = 1 到 18:
计算 b = 10^{k-1}。如果 b \ge n,跳出循环。计算 a = n - b。拼接:C =a + b。更新最大值,比较字符串长度与字典序。
时间复杂度
```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
string n_s;
cin>>n_s;
//用 stoll 把字符串转成 long long 进行计算
int n=stoll(n_s);
string best="";
//best表示最大拼接字符串
// 枚举 b 的位数 k
for (int k=1;k<=18;k++) {
int b=1;
for(int i=1;i<k;i++) {
b*=10; // b = 10^(k-1)
}
if(b>=n) break; // b 必须小于 N
int a=n-b;
// 使用字符串拼接避免溢出
string a_s=to_string(a);
string b_s=to_string(b);
// 拼接:a_s后面接 b_s
string c=a_s+b_s;
if(c.size()>best.size()||(c.size()==best.size()&&c>best)) {
best=c;
}
}
cout<<best;
return 0;
}
```
肥美的题解...