AcWing 792. 高精度减法

[toc]

第一讲 基础算法 - 04高精度 | Akari的小站

---

AcWing 792. 高精度减法【简单】

1 题目描述

给定两个正整数（不含前导 0），计算它们的差，计算结果可能为负数。

输入格式:
共两行，每行包含一个整数。

输出格式:
共一行，包含所求的差。

数据范围:
1 ≤ 整数长度 ≤ 10^5

输入样例：

32
11

输出样例：

21

2 算法步骤

1. 高精度数组利用字符串读入
2. 把字符串翻转存入两个整型数组 A, B
3. 若 A < B, 则交换 A, B, 输出负号 *
4. 从低位到高位, 逐位求差, 借位, 存差 *
5. 把数组 C 从高位到低位依次输出

3 时间复杂度

时间复杂度: O(n)

4 AC代码

4.1 数组

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int A[N], B[N], C[N];
int la, lb, lc;

bool cmp(int A[], int B[]);
void sub(int A[], int B[], int C[]);

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    string a, b;
    cin >> a >> b;
    la = a.size(), lb = b.size(), lc = max(la, lb);
    for (int i = la - 1; ~i; i -- ) A[la - 1 - i] = a[i] - '0';     // 翻转存入
    for (int i = lb - 1; ~i; i -- ) B[lb - 1 - i] = b[i] - '0';     // 翻转存入
    if (!cmp(A, B)) swap(A, B), cout << '-';        // 若 A < B, 则交换 A, B, 输出负号
    sub(A, B, C);
    for (int i = lc; ~i; i -- ) cout << C[i];       // 逆序输出
    
    return 0;
}

bool cmp(int A[], int B[]){
    if (la != lb) return la > lb;
    for (int i = la - 1; ~i; i -- )
        if (A[i] != B[i]) return A[i] > B[i];
    return true;    // 避免结果为 -0
}

void sub(int A[], int B[], int C[]){
    for (int i = 0; i < lc; i ++ ){
        if (A[i] < B[i])
            A[i + 1] --, A[i] += 10;    // 借位
        C[i] = A[i] - B[i];             // 存差
    }
    while (lc && C[lc] == 0) lc--;      // 处理前导0
}

4.2 vector

#include <bits/stdc++.h>
using namespace std;

typedef vector<int> VI;
VI A, B, C;

bool cmp(VI &A, VI &B);
void sub(VI &A, VI &B, VI &C);

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    string a, b;
    cin >> a >> b;
    for (int i = a.size() - 1; ~i; i -- ) A.push_back(a[i] - '0');      // 翻转存入
    for (int i = b.size() - 1; ~i; i -- ) B.push_back(b[i] - '0');      // 翻转存入
    if (!cmp(A, B)) swap(A, B), cout << "-";        // 若 A < B, 则交换 A, B, 输出负号
    sub(A, B, C);
    for (int i = C.size() - 1; ~i; i -- ) cout << C[i];     // 逆序输出
    
    return 0;
}

bool cmp(VI &A, VI &B){
    if (A.size() != B.size()) return A.size() > B.size();
    for (int i = A.size() - 1; ~i; i -- )
        if (A[i] != B[i]) return A[i] > B[i];
    return true;    // 避免结果为 -0
}

void sub(VI &A, VI &B, VI &C){
    int t = 0;      // t 存储借位
    for (int i = 0; i < A.size(); i++){
        t = A[i];
        if (i < B.size()) t -= B[i];
        if (t < 0) A[i + 1] --, t += 10;    // 借位
        C.push_back(t);                     // 存余
    }
    while (C.size() > 1 && !C.back()) C.pop_back();     // 处理前导0
}