Maximum Strength
题面翻译
题目描述
每一种材料的力量由一个十进制整数表示。
对于一个武器，由两种材料构成。假如第一种材料的力量为 \(X = \overline{x_1x_2 \dots x_n}\)，第二种材料的力量为 \(Y = \overline{y_1y_2 \dots y_n}\)，那么这个武器的力量为 \(\sum_{i = 1}^n |x_i - y_i|\)，也就是 \(|x_1 - y_1| + |x_2 - y_2| + \dots + |x_n - y_n|\)。
如果两个数字长度不一样，则要将短的数字用前导零补成相同长度。
现在，你拥有无数个力量在 \([L, R]\) 中的材料。你想要选出两个材料做出一个力量最大的武器。请你求出你设计出的武器力量的最大值。
题目描述
Fedya is playing a new game called "The Legend of Link", in which one of the character's abilities is to combine two materials into one weapon. Each material has its own strength, which can be represented by a positive integer $ x $ . The strength of the resulting weapon is determined as the sum of the absolute differences of the digits in the decimal representation of the integers at each position.
Formally, let the first material have strength $ X = \overline{x_{1}x_{2} \ldots x_{n}} $ , and the second material have strength $ Y = \overline{y_{1}y_{2} \ldots y_{n}} $ . Then the strength of the weapon is calculated as $ |x_{1} - y_{1}| + |x_{2} - y_{2}| + \ldots + |x_{n} - y_{n}| $ . If the integers have different lengths, then the shorter integer is padded with leading zeros.
Fedya has an unlimited supply of materials with all possible strengths from $ L $ to $ R $ , inclusive. Help him find the maximum possible strength of the weapon he can obtain.
An integer $ C = \overline{c_{1}c_{2} \ldots c_{k}} $ is defined as an integer obtained by sequentially writing the digits $ c_1, c_2, \ldots, c_k $ from left to right, i.e. $ 10^{k-1} \cdot c_1 + 10^{k-2} \cdot c_2 + \ldots + c_k $ .
输入格式
Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 500 $ ). The description of the test cases follows.
The first line of each test case contains two integers $ L $ and $ R $ ( $ 1 \le L \le R < 10^{100} $ ) — the decimal representation of the integers representing the minimum and maximum strength of the materials that Fedya has. It is guaranteed that the integers $ L $ and $ R $ do not contain leading zeros.
Note that the input data may not fit into standard $ 32 $ -bit or $ 64 $ -bit integer data types.
输出格式
For each test case print one integer — the maximum possible strength of the weapon that Fedya can obtain from the given materials.
样例 #1
样例输入 #1
6
53 57
179 239
13 37
132228 132228
54943329752812629795 55157581939688863366
88 1914
样例输出 #1
4
19
11
0
163
28
分析
当某个位置一个是9, 一个是0的时候, 他们的差值是最大的, 那我们考虑可不可以选出两个数, 使得其中一个的9尽可能多, 另一个的0尽可能多
对于上界R, 我们如果要让一个数从不是9变成9, 有很多限制, 如果要不使得上界增加, 我们还得选几个位置去缩小, 不仅麻烦, 且并不符合我们要找尽可能多的9的思路, 对于下界L要让非0变成0也是如此
那既然上界不能变大, 下界不能变小, 那我们就在下界基础上增加, 上界基础上减小, 保证数字仍在合法区间不就行了吗
!: 我们并不是改变上下区间, 只是在这个基础上增加减小, 以下说R变小L变大是为了方便叙述
我们只需要让R的最高位始终大于等于L的最低位, 那不管后边的数怎么变, R仍旧大于等于L, 且因为我们要在L上递增, R上递减, 所以就能保证我们找到的数字在合法的区间内了.
解释一下 check函数 的逻辑, 从高位往低位, R肯定至少有一位要比L大, 因为R是上界, L是下界, 我们从高位往低位遍历, 直到当前位置(不包括)为止, 只要有一位R比L大, 那就可以让R的这一位变成0, L的这一位变成9.
!: 数字太长先用 string 存然后一位一位放到 vector 里, 按照我的 get函数 和 check函数 的逻辑来看, vector的低位置放的是数字的低位, 但是 string 中数字的最高位是在0的位置, 我们读入后要记得 reverse 一下
代码
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 2e5 + 10;
vector<int> L, R;
string l, r;
bool check(int cur)
{
for(int i = R.size() - 1; i > cur; i--)
{
if(L[i] < R[i]) return true;
}
return false;
}
int get()
{
for(int i = 0; r[i]; i++)
{
R.push_back(r[i] - '0');
}
for(int i = 0; i < R.size(); i++)
{
if(i < l.size()) L.push_back(l[i] - '0');
else L.push_back(0); //L可能比R短, 所以要补前导0
}
int ans = 0;
for(int i = 0; i < R.size(); i++)
{
if(check(i)) //可以下边变9, 上边变0
{
ans += 9;
}
else ans += R[i] - L[i];
}
return ans;
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t; cin >> t;
while(t--)
{
cin >> l >> r;
reverse(l.begin(), l.end()), reverse(r.begin(), r.end());
cout << get() << endl;
L.clear(), R.clear();
}
}