题目描述

给定两个正整数，计算它们的差，计算结果可能为负数。

样例

32
11

21

算法

1. 减法的话，不能只比较A.size()和B.size()的大小，还存在size()一样大，但是A还是比B小的情况，比如222, 999这种情况，如果A和B相等，也应该是A - B，不然会多输出一个-。如果size()一样大，还是从高位开始比，比到最低位，A大的话就拿A-B。
2. 因为减法要借位，所以t表示借位，公式就是t = A[i] - t。对t的处理也很巧妙，if(t < 0) t = 1; else t = 0。
3. 处理前导零
4. 记得最后的return C，不然会SE，我怎么老忘这一步。。

时间复杂度

(枚举) $O(n^2)$

C++ 代码

#include <iostream>
#include <vector>

using namespace std;

const int N = 100010;

bool cmp(vector<int> A, vector<int> B)   // **1
{
    if(A.size() != B.size()) return A.size() > B.size();

    for(int i = A.size() - 1; i >= 0; i --)
        if(A[i] != B[i])
            return A[i] > B[i];

    return true;                            // **5
}

vector<int> sub(vector<int> &A, vector<int> &B)
{
    int t = 0;
    vector<int> C;

    for(int i = 0; i < A.size(); i ++)
    {
        t = A[i] - t;                 // **4
        if(i < B.size()) t -= B[i];

        C.push_back((t + 10) % 10);

        if(t < 0) t = 1;              // **4
        else t = 0;
    }

    while(C.size() > 1 && C.back() == 0) C.pop_back();   // **2

    return C;   // **3
}

int main()
{
    string a, b;
    vector<int> A, B;
    cin >> a >> b;

    for(int i = a.size() - 1; i >= 0; i --) A.push_back(a[i] - '0');
    for(int i = b.size() - 1; i >= 0; i --) B.push_back(b[i] - '0');

    vector<int> C;

    if(cmp(A, B)) C = sub(A, B);    // **1
    else
    {
        printf("-");
        C = sub(B, A);
    }

    for(int i = C.size() - 1; i >= 0; i --) cout << C[i];

    return 0;
}