C++スタックとキューの応用


ああ!この問題はどうしてブログを書きますか.私は知的障害者ですか?いいえ私は違います!!!私はただこの問題に穴をあけられただけだ.私が最近あまりにもがっかりして問題を書くのが好きではないのかもしれません.(✺ω✺)最初はスタックとキューをきちんと書いていたが、結局穴に落ちてしまった.私は標準ライブラリでスタックとキューを直接手書きしなかった.300行のコードがバグを出して直したくないので、何日もこの問題を提出しなかった(実は私は馬鹿だった).そして私はこの問題をあまりにも機知に富んでいる.OK次は問題を見て、くだらない話はもうやめました!!!
まず注意点を言います.
  • 問題の要求に従って書くなら、よく問題を読みます.1.1離れた車は頭の上にいないかもしれませんが、真ん中にいます.
  • 第2ピット:車が離れ、駐車場内に車がいない場合は、ここまでです.この車が歩道にないことを考えないでください.
  • 駐車場から1台の車が離れた後、歩道の別の車が補位されると、駐車場に入る時間が前の車が離れた時間になります.
  • 題Aが出てきましたが、チェーンメーターで書いてありました・・・最近ちょっと喪に入ってしまいました(´;ω;`)気分がよくなったら標準的な答えを補充します......
  • 駐車場を設けるのはn台の自動車を停めることができる狭い通路で、自動車の出入りを可能にするドアは1つしかありません.車は駐車場内で車の到着時間の前後順に北から南へ並んでいる(ゲートは最南端にあり、最初に到着した最初の車は駐車場の最北端に駐車されている).駐車場内にn台の車がいっぱい駐車されていると、後の車はドアの外の歩道で待つしかなく、車が出ると、歩道に並んだ最初の車が駐車場に入る.駐車場内のある車が離れる場合、その後に入った車両はまず駐車場を離れて道を譲らなければならない.この車がドアの外に出るまで、他の車両は元の順序で駐車場に入る.駐車場に駐車している車ごとに駐車場を離れるときは、滞在時間の長さに応じて料金を払わなければなりません.駐車場に上記の要求に従って管理するシミュレーションプログラムを作成してみます.▶ Tips:緑の字を見ましたか.これがあなたが通常通りにしないことを決める鍵です.もしあなたがこの言葉に従って書いて、STLを使わないなら、あなたは罪を探していますが、よく練習したいなら、人の要求に従って書いてください.
    入力:入力データの最初の行には、駐車場の容量と1時間あたりの駐車料金をそれぞれ表す2つの正の整数nとm(n,m<=10)が含まれています.2行目から、各行に1組の入力データが表示され、3つの内容で構成されています.
  • 大文字の英字で、自動車の「到着」または「離脱」情報を表します.
  • 「A」を入力と、自動車が
  • に達したことを示す.
  • 「D」を入力と、車が離れることを示す
  • 「E」を入力すると、プログラムが終了することを示す.

  • 正の整数Xで、自動車のナンバープレートを表します.
  • は、自動車が到着または離脱した時刻を表す正の整数Tである.

  • この3つの内容の間にはスペースがあります.
    出力:各入力データのセットを操作した出力情報は、車両が到着すると、駐車場内または歩道上の自動車の駐車位置を出力する.車が離れると、駐車場に車が滞在する時間(単位は時間)と納めるべき費用(歩道に滞在する時間は有料ではない)を出力し、駐車料金は1時間m元と仮定する.具体的には、次のような状況に分けられます.
  • 自動車Xが到着し、かつ駐車場が満杯でない場合、「自動車Xは駐車場Y号に停車する」(ただし、Xは自動車ナンバープレート、Yは駐車場ナンバープレート、1≦Y≦n)
  • という情報を出力する.
  • 自動車Xが到着したが、駐車場が満杯になった場合、「自動車Xは歩道のZ号位置に停車する」(ただし、Xは自動車ナンバープレート、Zは歩道の駐車スペース番号、1≦Z)
  • 自動車Xが退去し、かつXが駐車場内にある場合、「自動車XがH時間停車し、駐車料金M元を納める」(ただし、Xは自動車ナンバープレート、Hは駐車時間、Mは駐車料金)3.1このとき歩道上の駐車列が空でない場合、歩道上の最初の自動車を駐車場に停める、「自動車Xは駐車場Y号に停車する」(うち、Xは自動車ナンバー、Yは駐車場ナンバー、1≦Y≦n)
  • を出力する.
  • 自動車Xが離れているが、駐車場にナンバープレートXがない自動車は、「自動車Xは駐車場にいない」(ただし、Xは自動車ナンバープレート)
  • という情報を出力する.
    サンプル入力:
    4 5 A 1 10 A 2 15 A 3 16 D 4 17 D 3 20 A 4 21 A 5 22 A 6 23 A 7 24 A 8 25 D 3 25 D 4 25 D 5 26 A 9 26 A 10 27 A 11 28 A 12 29 A 13 30 D 13 35 D 1 36 D 2 37 D 3 38 D 4 38 D 5 38 D 6 38 D 7 39 D 8 40 D 9 41 D 10 44 D 11 46 D 12 50 D 13 60 D 14 70 E
    ▶ Tips:この3行の赤いのを見ましたか.間違いなくナンバープレート13で、彼は2回出かけました!!!だからあなたはいつものように考えてはいけません.もしこの車が駐車場にいなかったら、彼が離れたら、彼は歩道にいるかもしれないと思っていたが、それも行かせなければならないだろう.結局私は考えすぎました.もしそれが歩道にあれば、彼と一緒に行きましょう.(以下、私のコードはコメントされています)
    サンプル出力:
    車1は駐車場1番に停車します車2は駐車場2番に停車します車3は駐車場3番に停車します車4は駐車場ではありません車3は4時間停車します駐車料金20元を払って車4が駐車場3号に停車する位置自動車5が駐車場4号に停車する位置自動車6が歩道に停車する1号位置自動車7が歩道に停車する2号位置自動車8が歩道に停車する3号位置自動車3が駐車場に停車しない4時間、駐車料金20元を払って車6が駐車場4号位置自動車5に停車して4時間、駐車料金20元を払って車7が駐車場4番に停車する位置自動車9が歩道に停車する2番の位置自動車10が歩道に停車する3番の位置自動車11が歩道に停車する4番の位置自動車12が歩道に停車する5番の位置自動車13が歩道に停車する6番の位置自動車13が駐車場自動車1に26時間停車しない.駐車料金130元を払う自動車8は駐車場4号に停泊する自動車2は22時間、駐車料金110元を払う自動車9は駐車場4号に停泊する自動車3は駐車場にいない自動車4は駐車場にいない自動車5は駐車場にいない自動車6は13時間、駐車料金65元を払う自動車10は駐車場4号に停泊する自動車7は13時間、駐車料金65元を納める自動車11は駐車場4号に停泊する自動車8は4時間、駐車料金20元を納める自動車12は駐車場4号に停泊する自動車9は4時間、駐車料金20元を納める自動車13は駐車場4号に停泊する自動車10は6時間、駐車料金30元を納める自動車11は7時間、駐車料金35元を納める自動車12は10時間、駐車料金50元を払って車を13駐車して19時間、駐車料金95元を払って車を14駐車場にいません
    ヒント:別のスタック(チェーン構造でも実現)を設置し、立ち去る車に道を譲って駐車場から退く車に臨時に駐車する必要があります.スタックの各要素は1台の自動車を表し、2つのデータ項目を含む:自動車のナンバープレート番号と駐車場に入る時刻.▶ Tips:これは要求通りにまじめに書いた人にヒントです.
    回答1:私は直接サボってチェーン時計で書いたのですが…
    #include
    using namespace std;
    struct Node
    {
        int data;
        int time;
        Node *next;
    };
    class car
    {
    public:
        car(){head=new Node; head->next=NULL;}
        ~car(){};
        void in(int m,int n);
        void pop();
        void leave(int m);
        int getlic(int n);
        int gettime(int n);
        int find(int n);
    private:
        Node *head;
    };
    void car::in(int m,int n)
    {
        Node *p=head;
        while(p->next!=NULL)
            p=p->next;
        Node *s=new Node;
        s->data=m;
        s->time=n;
        p->next=s;
        s->next=NULL;
    }
    void car::pop()
    {
        Node *p=head->next;
        head->next=p->next;
        delete p;
    }
    void car::leave(int m)
    {
        Node *p=head;
        for (int i=0;i<m-1;i++)
        {
            p=p->next;
        }
        Node *q=p->next;
        p->next=q->next;
        delete q;
    }
    int car::gettime(int n)
    {
        Node *p=head;
        for (int i=0;i<n;i++)
        {
            p=p->next;
        }
        return p->time;
    }
    int car::getlic(int n)
    {
        Node *p=head;
        for (int i=0;i<n;i++)
        {
            p=p->next;
        }
        return p->data;
    }
    int car::find(int n)
    {
        Node *p=head;
        int count=0;
        while(p->next!=NULL)
        {
            count++;
            p=p->next;
            if (p->data==n)
                return count;
        }
        return 0;
    }
    int main()
    {
        car Park,Road;
        int cpark=0,croad=0,capacity,money,time,license;
        cin>>capacity>>money;
        char instruction;
        while(cin>>instruction)
        {
            if(instruction=='E') break;
            cin>>license>>time;
            if (instruction=='A')
            {
                if (cpark<capacity)
                {
                    cpark++;
                    Park.in(license,time);
                    cout<<"  "<<license<<"      "<<cpark<<"   "<<endl;
                } 
                else
                {
                    croad++;
                    Road.in(license,time);
                    cout<<"  "<<license<<"      "<<croad<<"   "<<endl;
                }
            } 
            else if(instruction=='D')
            {
                int flag=Park.find(license);
                if(flag==0)
                {
                    cout<<"  "<<license<<"     "<<endl;
                    /*flag=Road.find(license);
                    if (flag!=0)
                    {
                        Road.leave(flag);
                    }*/
                }
                else
                {
                    int result=time-Park.gettime(flag);
                    cout<<"  "<<license<<"  "<<result<<"  ,     "<<result*money<<" "<<endl;
                    Park.leave(flag);
                    cpark--;
                    if (croad>0)
                    {
                        croad--;cpark++;
                        Park.in(Road.getlic(1),time);
                        cout<<"  "<<Road.getlic(1)<<"      "<<cpark<<"   "<<endl;
                        Road.pop();
                    }
                }
            }
        }
        return 0;
    }
    
    

    答案2:ええ、これはほかの人が書いたもので、表面的にはスタックと行列になっています.
    #include
    using namespace std;
     
    struct data1
    {
        int code;
        int T;
    };
     
    struct queue
    {
        data1 a[1000];
        int head;
        int tail;
    };
     
    struct stack
    {
        data1 a[1000];
        int top;
    };
     
    int main()
    {
        char flag;
        int code, T;
        queue q;
        q.head = 1;
        q.tail = 1;
        stack s1;
        s1.top = 0;
        int n, m;
        cin >> n >> m;
        while (cin >> flag)
        {
            if (flag == 'E') break;
            cin >> code >> T;
            if (flag == 'A')
            {
                if (s1.top < n)
                {
                    s1.top++;
                    s1.a[s1.top].code = code;
                    s1.a[s1.top].T = T;
                    cout << "  " << code << "      " << s1.top << "   " << endl;
                }
                else
                {
                    q.a[q.tail].code = code;
                    q.a[q.tail].T = T;
                    cout << "  " << code << "      " << q.tail << "   " << endl;
                    q.tail++;
                }
            }
            else if (flag == 'D')
            {
                int book = 0;
                int i;
                for (i = 1; i <= s1.top; i++)
                {
                    if (code == s1.a[i].code)
                    {
                        book = 1;
                        break;
                    }
                }
                if (book == 0)
                {
                    cout << "  " << code << "     " <<endl;
                }
                else
                {
                    int t = T - s1.a[i].T;
                    for (int j = i; j < s1.top ; j++)
                    {
                        s1.a[j].code = s1.a[j + 1].code;
                        s1.a[j].T = s1.a[j + 1].T;
                    }
                    int cost = m * t;
                    cout << "  " << code << "  " << t << "  ,     " << cost << " " << endl;
                    if (q.head < q.tail)
                    {
                        s1.a[s1.top].code = q.a[q.head].code;
                        s1.a[s1.top].T = T;
                        q.tail--;
                        for (int j = q.head; j < q.tail; j++)
                        {
                            q.a[j].code = q.a[j + 1].code;
                            q.a[j].T = q.a[j + 1].T;
                        }
                        cout << "  " << s1.a[s1.top].code << "      " << s1.top << "   " << endl;
                    }
                    else
                    {
                        s1.top--;
                    }
                }
            }
        }
        return 0;
    }
    
    

    ロリアンです.(´;ω;`)プログラム媛になるように頑張ります...