ホテルの部屋割り当て-C++

質問する

問題の説明
[この問題は精度と効率テストで1点ずつ占めています]
「雪城」でホテルを経営する「スカビー」は、ホテルにチェックインしたお客様のために部屋を手配したいと思っています.ホテルにはk部屋があり、1号室からk号室まで番号がついています.最初は、すべての部屋が空いていたので、「CC」は次のルールに従ってお客様の部屋を手配しようとしました.
一度に一人で申請の順番に部屋を手配します.
お客様がチェックインしたい部屋番号を提出します.
お客様が希望する部屋が空いている場合は、すぐに手配してください.
部屋が割り当てられている場合は、希望する部屋より大きい番号の部屋を選択し、空き部屋の中で一番小さい番号の部屋を選択します.
たとえば、合計10個の部屋があり、お客様が希望する部屋番号が[1,3,4,1,3,1]の順であれば、次のように部屋を割り当てます.
必要な部屋番号は割り当てられています
1 1
3 3
4 4
1 2
3 5
1 6

せいげんじょうけん

kは1以上1012以下の自然数である.
room number配列のサイズは200000を超えない.
room number配列の各要素の値はkより大きい自然数である.
room number配列は、すべてのお客様が部屋を割り当てることができる場合にのみ入力されます.
例えば、k=5、room number=[5,5]などの場合は、お客様が部屋を割り当てることができないため、入力として使用しません.

問題を解く

これはかなり難しい問題です.最初はpythonでlist popと単純にソートし,効率部分を通過しなかった.
重要なのは、制限事項の範囲から、有効な探索を行い、部屋を割り当てることができない顧客が現れないことです.
上記の制限を考慮すると、入居者は入居したい部屋に入るか、入居したい部屋より大きくて空いている部屋の中で番号が一番小さい部屋に入る.
当たり前じゃないですか?そう考えてもいいですが、どんな状況なのかよく考えたほうがいいです.
必ず自分でやらなければならない時間があります1中に入ると1中に誰もいないことを確認して中に入りましたあと1が欲しい人がいれば、希望する部屋よりも広く、空いている部屋の中で一番番号の小さい部屋に泊まることができます.
満室であれば、他の部屋を探索する際にx+1号室から探索し、探索する部屋が空いていれば終了する.

#include <string>
#include <vector>
#include <map>

using namespace std;

map<long long , long long> R;

long long Find (long long n)
{
	//탐색하는 방이 비어있으면 방을 return;
    if(R[n] == 0) return n;
    //탐색하는 방이 차있으면 빈 방이 있을때 까지 찾아줌.
    else return R[n] = Find(R[n]);
}

vector<long long> solution(long long k, vector<long long> room_number) {
    vector<long long> answer;
    
    for (int i = 0 ; i < room_number.size() ; i ++)
    {
        long long Num = room_number[i];
        
        if (R[Num] == 0)
        {
            answer.push_back(Num);
            //Num +1은 본인보다 큰 방 중에 선택해야하기 때문임.
            R[Num] = Find(Num+1);
        }
        else{
            long long Next_Num = Find(Num);
            answer.push_back(Next_Num);
            R[Next_Num] = Find(Next_Num+1);
        }
    }
    
    return answer;
}