d166: 反轉表

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

相關文章

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *