d166 - 反轉表
題目描述
題目給定一個反轉表，其中每個元素表示該數字在原始數列中，其前面有多少個比它大的數字。要求根據反轉表重建原始數列。
解題思路
這題的核心思想是利用反轉表中的資訊，逐步確定每個數字在原始數列中的位置。我們可以將數字按照其值排序，然後根據反轉表中的資訊，將每個數字放置到正確的位置上。具體來說，對於反轉表中的每個元素，我們需要找到一個位置，使得該位置前面有指定數量的比它大的數字。這可以使用貪心策略來實現：每次將最小的數字放置到滿足反轉表條件的最左邊的位置。
複雜度分析
- 時間複雜度: O(n^2)，其中 n 是數列的長度。排序需要 O(n log n)，但最內層的迴圈查找位置需要 O(n)。
- 空間複雜度: O(n)，用於儲存輸入數列、反轉表和輸出數列。
程式碼
#include <iostream>
using namespace std;
string s;
int main(){
while(getline(cin,s)){
if(s[0]=='-')break;
else if(s[0]>='0'){
s+=' ';
int tmp=-1,a[51]={0},ans[51]={0},it=0;
for(int i=0;i<s.length();++i){
if(s[i]>='0'&&s[i]<='9'){
if(tmp==-1)tmp=0;
tmp*=10;
tmp+=s[i]-'0';
}
else{
if(tmp!=-1){
a[it]=tmp;
++it;
tmp=-1;
}
}
}
for(int i=0;i<it;++i){
tmp=a[i];
for(int j=0;j<it;++j){
if(ans[j]==0&&tmp==0){
ans[j]=i+1;
j=it;
}
else if(ans[j]==0){
--tmp;
}
}
}
for(int i=0;i<it;++i){
cout << ans[i] << " ";
}
cout << "\n";
}
}
}