a884 - 11448 - Crisis
題目描述
題目要求計算兩個大整數的差，輸入包含多組測試案例，每組案例包含兩個整數 A 和 B，輸出 A - B 的結果。需要處理負數以及大數運算，因為輸入的數字可能超過一般整數型態的範圍。
解題思路
此題的核心在於處理大數的減法。由於輸入的數字可能很大，無法直接使用內建的整數型態進行計算，因此需要將數字轉換為字串，然後模擬手動計算減法的過程。程式碼首先讀取兩個字串表示的數字，判斷哪個數字較大，並確定減法的方向。然後，將數字對齊，從最低位開始逐位進行減法運算，處理進位和借位。最後，將結果轉換為字串輸出。
複雜度分析
- 時間複雜度: O(max(len(a), len(b)))，其中 len(a) 和 len(b) 分別是字串 a 和 b 的長度。這是因為程式碼需要遍歷字串的每一位進行減法運算。
- 空間複雜度: O(max(len(a), len(b)))，主要用於儲存結果的陣列 an。
程式碼
#include <iostream>
using namespace std;
int main(){
string a,b;
cin >> a;
while(cin >> a){
cin >> b;
int al=a.length(),bl=b.length(),an[al+bl];
bool f=0,big=0;
if((a[0]=='-'&&b[0]!='-')||(al>bl&&a[0]=='-'&&b[0]=='-'))big=1;
if(al==bl&&a[0]=='-'&&b[0]=='-')
for(int i=0;i<al;++i){
if(a[i]>b[i])big=1;
if(a[i]!=b[i])break;
}
if(bl==al&&a[0]!='-'&&b[0]!='-')
for(int i=0;i<al;++i){
if(a[i]<b[i])big=1;
if(a[i]!=b[i])break;
}
if((bl>al&&a[0]!='-'&&b[0]!='-')||big==1){
al^=bl;bl^=al;al^=bl;
string tmp;
tmp=a;a=b;b=tmp;
f=1;
}
for(int i=al+bl-1;i>=0;--i)an[i]=0;
if(a[0]=='-')
for(int i=1;i<al;++i)
an[i-1]-=(a[al-i]-'0');
else
for(int i=0;i<al;++i)
an[i]=(a[al-i-1]-'0');
if(b[0]=='-')
for(int i=1;i<bl;++i)
an[i-1]+=(b[bl-i]-'0');
else
for(int i=0;i<bl;++i)
an[i]-=(b[bl-i-1]-'0');
for(int i=0;i<al+bl;++i){
if(an[i]<0){
an[i+1]--;
an[i]+=10;
}
else if(an[i]>9){
an[i+1]++;
an[i]-=10;
}
}
if(f==1)cout << '-';
int start=0;
for(int i=al+bl-1;i>=0;--i)
if(an[i]!=0){
start=i;
break;
}
for(int i=start;i>=0;--i)
cout << an[i];
cout << "\n";
}
}