UVa10035
題敘
http://domen111.github.io/UVa-Easy-Viewer/?10035
給兩個十位數，求相加過程中進位幾次
想法
直接模擬一遍加法的作法
從最低位開始相加，如果有進位記錄進位多少，再將答案遞增即可
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
#include<bits/stdc++.h>
#define LL long long
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define pii pair<int,int>
using namespace std;
string a,b;
int cnt=0;
void solve(){
int A=a.size()-1,B=b.size()-1;
int carry=0,num_A,num_B;
while(A>=0 || B>=0){
num_A=(A<0) ? 0 : a[A]-'0';
num_B=(B<0) ? 0 : b[B]-'0';
if(num_A+num_B+carry>9){
carry=(num_A+num_B+carry)/10;
cnt++;
}
else
carry=0;
A--,B--;
}
}
int main(){
IOS
while(cin>>a>>b && (a!="0" || b!="0")){
cnt=0;
solve();
if(cnt>1)
cout<<cnt<<" carry operations.\n";
else if(cnt==1)
cout<<"1 carry operation.\n";
else
cout<<"No carry operation.\n";
}
return 0;
}
|
複雜度
對每個位數做處理，每個位數處理時間複雜度為 $O(1)$
總時間複雜度為 $O(max(len(A),len(B)))$