2022.11.19 AM 10:00 by CBJ
來源 : https://zerojudge.tw/ShowProblem?problemid=d166 出題者 : w11123 標籤 : 陣列、貪心法則 難易度 : 2
解題想法 : 數字應該要放在哪裡呢? 就是由所謂的「反轉表」來決定，我們會以題目的範例測資作為反轉表的範例。 反轉表s[] : [2, 3, 6, 4, 0, 2, 2, 1, 0] 首先我們看到反轉表的第一個位置是2，表示1的前面會有2個比他大的數，所以我們必須要預留這些位置，為了保證預留的位置是剛好的，我們得從小到大找位置，也就是從1開始放。 為何從小到大放一定會是正確的呢? 範例中反轉表1的值是2，所以我們會保留2個「0」在前面，因為是從小到大放，所以後續不論是誰都比1大，所以不管是誰放在預留的「0」上面，都會是成立的。 設反轉表的數字為k，答案陣列設為ans[]，cnt記錄0出現的次數，要放的數是i。 實作上為了方便我們可以先將ans[]全部先填0，因此我們就從ans[]的第一項開始找，並隨時記錄cnt，遇到0就把cnt+=1，當cnt等於k+1時，表示前面已經預留了k個「0」，k+1就會是i應該要放的位置。 照著這個規律下去實作就可以解決此題。 (注意 : 題目雖然沒有提到，但是需要反覆讀取直到檔案結尾)
//C++ language
//solution link(含註解):
#include<iostream>
#include<vector>
#include<string>
#include<sstream>
using namespace std;
int main(){
string s;
while(getline(cin,s)){
if(s=="-1") break;
stringstream ss(s);
vector<int>v;
int n;
for(int i=0;ss>>n;i++){
v.push_back(n);
}
vector<int>ans(v.size(),0);
for(int i=0;i<v.size();i++){
int cnt=0;
for(int j=0;j<ans.size();j++){
if(ans[j]==0){
cnt++;
}
if(cnt==v[i]+1){
ans[j]=i+1;
break;
}
}
}
for(int i:ans){
if(i==0) break;
else cout<<i<<" ";
}
cout<<"\n";
}
}
## Python language
## solution link(含註解):
try:
while True:
s=[int(x) for x in input().split()]
if s==[-1]: break
ans=[0]*len(s)
for i in range(len(s)):
cnt=0
for j in range(len(ans)):
if ans[j]==0:
cnt+=1
if cnt==s[i]+1:
ans[j]=i+1
break
print(*ans,sep=' ')
except EOFError: pass
發佈留言