e633 - 10800 - Not That Kind of Graph
題目描述
題目要求根據輸入字串 (包含 'R', 'F', 'C') 繪製股價走勢圖。'R' 代表股價上漲，'F' 代表股價下跌，'C' 代表股價持平。圖形使用 '/', '\', '_' 字元表示股價變化。
解題思路
程式碼模擬了股價走勢圖的繪製過程。它使用一個二維陣列 a 來記錄每個時間點的股價變化，並使用 r 陣列來記錄每個位置的最高索引。程式碼遍歷輸入字串，根據字元更新 a 和 r 陣列。最後，程式碼根據 a 陣列繪製股價走勢圖。核心邏輯是根據輸入字串的 'R', 'F', 'C' 決定在圖中繪製 '/', '\', '_' 字元。
複雜度分析
- 時間複雜度: O(n^2)，其中 n 是輸入字串的長度。這是因為程式碼需要遍歷輸入字串，並且在繪製圖形時需要遍歷
r陣列。 - 空間複雜度: O(n^2)，因為程式碼使用了一個大小為 105x105 的二維陣列
a和一個大小為 105 的陣列r。
程式碼
#include <iostream>
using namespace std;
int t,a[105][105],r[105];
string s;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cout.tie(0);
cin >> t;
for(int ca=1;ca<=t;++ca){
cin >> s;
int ct=50,mi=50,ma=50,dd=1;
for(int i=0;i<=100;++i){
r[i]=0;
for(int j=0;j<=100;++j)
a[i][j]=0;
}
for(int i=0;i<s.size();++i){
if(s[i]=='R'){
a[i][ct]=1;
r[ct]=i;
ma=max(ma,ct);
mi=min(ct,mi);
++ct;
}
else if(s[i]=='F'){
a[i][ct-1]=2;
r[ct-1]=i;
ma=max(ma,ct-1);
mi=min(ct-1,mi);
--ct;
}
else{
a[i][ct]=3;
r[ct]=i;
ma=max(ma,ct);
mi=min(ct,mi);
}
}
cout << "Case #" << ca << ":\n";
for(int j=0;j<s.size();++j)
if(a[j][ma])dd=0;
ma-=dd;
for(int i=ma;i>=mi;--i){
cout << "| ";
for(int j=0;j<=r[i];++j){
if(a[j][i]==1)
cout << "/";
else if(a[j][i]==2)
cout << "\\";
else if(a[j][i]==3)
cout << "_";
else
cout << " ";
}
cout << "\n";
}
cout << "+--";
for(int j=0;j<s.size();++j)
cout << '-';
cout << "\n\n";
}
}