j244 - 111北二3a.兌獎問題
題目描述
題目給定三個中獎號碼 a, b, c 和 n 個購買的號碼 s。對於每個購買的號碼，計算其與三個中獎號碼的差異，並根據差異程度給予不同的獎金。目標是計算所有購買號碼的總獎金。
解題思路
這題的核心是比較每個購買的號碼 s 與三個中獎號碼 a, b, c 的差異。比較差異的方式是從最高位開始，直到找到第一個不同的位數。差異的程度由第一個不同位數的位置決定。程式碼使用迴圈迭代每個購買的號碼，並使用三個迴圈分別與三個中獎號碼進行比較。t 變數記錄了最大差異程度，然後根據 t 的值給予相應的獎金。獎金的計算是貪婪的，即根據差異程度選擇最高的獎金。
複雜度分析
- 時間複雜度: O(n * k * 3) = O(n * k)，其中 n 是購買號碼的數量，k 是號碼的長度。
- 空間複雜度: O(k)，主要用於儲存中獎號碼和購買號碼的字串。
程式碼
#include <iostream>
using namespace std;
int n,k;
long long ans;
string a,b,c,s;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> k >> n >> a >> b >> c;
a='o'+a;
b='o'+b;
c='o'+c;
while(n--){
cin >> s;
s='x'+s;
int t=0;
for(int i=k;i>=0;--i){
if(s[i]!=a[i]){
t=max(t,k-i);
break;
}
}
for(int i=k;i>=0;--i){
if(s[i]!=b[i]){
t=max(t,k-i);
break;
}
}
for(int i=k;i>=0;--i){
if(s[i]!=c[i]){
t=max(t,k-i);
break;
}
}
if(t==k){
ans+=500000;
}
else if(t>=k-2){
ans+=10000;
}
else if(t>=k-4){
ans+=1000;
}
else if(t>=3){
ans+=300;
}
}
cout << ans;
}