Programmers多段歯ブラシ販売

12741 ワード
programmers algorithm cpp テキストリンク
😄 第三段階はやっぱり難しくて面白い
  • 最初はクリスマスツリーの問題だと思っていた.(図は木)
  • でも問題をよく見ると、自分から親まで、お金を交代で分ける形の問題です.
  • ・string使うべきだと思うmap自分の親を貯める.
  • map<string,int>:自分が持っているお金
  • map<string,string>:自分の両親
    •     m["-"] = 0;
    for(int i=0;i<enroll.size();i++)
    {
        m[enroll[i]]=0;
        parent[enroll[i]] = referral[i];
    }
  • ・center印刷する必要がないのかわからず、ずっと印刷しています.
  • 自分のお金を0に初期化parentも初期化した.(enroll, referralベクトル使用)
    •     for(int i=0;i<seller.size();i++)
    {
        string me = seller[i];
        int coin = amount[i]*100;
        while(me !="-" && coin/10 >= 1 )
        {
            m[me] += (coin - coin/10);
            coin = coin/10;
            me = parent[me];
        }
        m[me] += (coin);
    }
  • 残りが1元未満なら、私が最上階ならwhileドアから逃げ出します.
  • 保存できないので保存しなければならない
  • しかし問題が終わった後、他の人がcoin/10 >= 1条件を与えていないことに気づいた.
  • なぜですか?考えてみれば、どうせ0元なら、ずっと親になるし、0元を加えても同じだ.
  • 筆者は、1元未満であれば、親にも上がらせないように条件を付けておけば、他の人もどうせ養育で親の数まで上がることはないので、上がらせたと思う.
    • 💻完全なコード
    #include <string>
#include <vector>
#include <unordered_map>
#include <iostream>

using namespace std;

unordered_map<string,int>m;
unordered_map<string,string>parent;

vector<int> solution(vector<string> enroll, vector<string> referral, vector<string> seller, vector<int> amount) {
    vector<int> answer;
    
    m["-"] = 0;
    for(int i=0;i<enroll.size();i++)
    {
        m[enroll[i]]=0;
        parent[enroll[i]] = referral[i];
    }
    
    for(int i=0;i<seller.size();i++)
    {
        string me = seller[i];
        int coin = amount[i]*100;
        while(me !="-" && coin/10 >= 1 )
        {
            m[me] += (coin - coin/10);
            coin = coin/10;
            me = parent[me];
        }
        m[me] += (coin);
    }
    
    for(int i=0;i<enroll.size();i++)
    {
        answer.push_back(m[enroll[i]]);
    }
    
    return answer;
}
    バブルソート
    DAY - 11