g798 - 帶動商機 (Business)
題目描述
題目給定一串數字，代表每個商店的銷售額。每一輪迭代中，如果一個商店的銷售額比其相鄰商店高，則相鄰商店的銷售額會增加一定比例（邊界商店為 10%，中間商店為 5%）。重複此過程 d 輪，最後輸出每一家商店的最終銷售額。
解題思路
此題的核心是模擬銷售額的變化。程式使用一個二維陣列 a 儲存每個商店的原始銷售額和每一輪迭代後的銷售額。在每一輪迭代中，程式遍歷每個商店，並檢查其是否比相鄰商店的銷售額高。如果是，則相鄰商店的銷售額會增加相應的比例。在每一輪迭代結束後，程式將每一家商店的銷售額更新為當輪的銷售額。
複雜度分析
- 時間複雜度: O(n*d)，其中 n 是商店數量，d 是迭代次數。因為程式需要對每個商店進行 d 次迭代。
- 空間複雜度: O(n)，因為程式使用一個大小為 n 的陣列來儲存商店的銷售額。
程式碼
#include <iostream>
using namespace std;
int a[35][2],n,d;
int main(){
while(cin >> a[n][0]){
if(a[n][0]==0)break;
++n;
}
cin >> d;
while(d){
--d;
for(int i=0;i<n;++i){
a[i][1]=a[i][0];
}
for(int i=0;i<n;++i){
if(i==0){
if(a[i][0]>a[i+1][0]){
a[i+1][1]+=a[i][0]*0.1;
}
}
else if(i==n-1){
if(a[i][0]>a[i-1][0]){
a[i-1][1]+=a[i][0]*0.1;
}
}
else{
if(a[i][0]>a[i+1][0]){
a[i+1][1]+=a[i][0]*0.05;
}
if(a[i][0]>a[i-1][0]){
a[i-1][1]+=a[i][0]*0.05;
}
}
}
for(int i=0;i<n;++i){
a[i][0]=a[i][1];
}
}
for(int i=0;i<n;++i){
cout << a[i][0] << " ";
}
}