AcWing0792 高精度减法
给定两个正整数(不含前导 0),计算它们的差,计算结果可能为负数。
输入格式
共两行,每行包含一个整数。
输出格式
共一行,包含所求的差。
数据范围
1≤整数长度≤105
输入样例:
32
11
输出样例:
21
算法1:
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
const int BASE = 10;
// 如果x >= y,返回true
bool cmp(vector<int>& x, vector<int>& y) {
if (x.size() != y.size()) {
return x.size() > y.size();
}
for (int i = x.size() - 1; i >= 0; i--) {
if (x[i] != y[i]) {
return x[i] > y[i];
}
}
return true;
}
// sign为符号位, 1表示负,0表示正
vector<int> sub(vector<int>& x, vector<int>& y, bool& sign) {
vector<int> res;
if (!cmp(x, y)) {
res = sub(y, x, sign);
sign = 1;
return res;
}
int b = 0;
for (int i = 0; i < x.size(); i++) {
int dif = x[i] - b;
b = 0;
if (i < y.size()) {
dif -= y[i];
}
if(dif < 0) {
dif += BASE;
b = 1;
}
res.push_back(dif);
}
while (res.size() > 1 && res.back() == 0) {
res.pop_back();
}
sign = 0;
return res;
}
int main() {
string s1, s2;
cin >> s1 >> s2;
vector<int> v1, v2;
for (int i = s1.size() - 1; i >= 0; i--) {
v1.push_back(s1[i] - '0');
}
for (int i = s2.size() - 1; i >= 0; i--) {
v2.push_back(s2[i] - '0');
}
bool sign;
vector<int> res = sub(v1, v2, sign);
if (sign) {
cout << '-';
}
for (int i = res.size() - 1; i >= 0; i--) {
cout << res[i];
}
return 0;
}