C++酒店预订系统两种实现结果不一致问题排查

需求说明 #

需要开发酒店预订系统，支持客户订房及酒店方管控，处理三类事件：

• BOOK time hotel_name client_id room_count：客户client_id在time时刻预订hotel_name酒店的room_count间房间，时间单位为秒。
• CLIENTS hotel_name：统计以最后一次BOOK事件的current_time为准，过去24小时（current_time-86400 < time ≤ current_time）内，在hotel_name酒店预订过房间的不同客户数量。
• ROOMS hotel_name：统计上述时间范围内hotel_name酒店的总预订房间数。

问题描述 #

第一种实现方案中，每次BOOK操作会清理所有酒店的过期记录，能通过隐藏测试但运行缓慢。将清理逻辑迁移至CLIENTS和ROOMS方法中实现第二种方案后，在某隐藏测试中出现"wrong answer"错误，两种方案功能逻辑应一致，但无法定位问题。

实现代码 #

第一种实现代码 #

#include <iomanip>
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <utility>
#include <deque>

using namespace std;

class HotelManagement {

public:

  HotelManagement() : hotel_rooms(), hotel_time(){}

  void Book (int &time, string &hotel_name, int &client_id, int &room_count){
    hotel_rooms[hotel_name].push_back(room_count);
    hotel_time[hotel_name].push_back(time);

    for (auto &pair : hotel_time){
         while(hotel_time.at(pair.first).front() <= time - 86400){
          if (!pair.second.empty()){
            hotel_time.at(pair.first).pop_front();
            hotel_rooms.at(pair.first).pop_front();
          }
      }
    }
  }

  int Clients(string &hotel_name){
    deque<int>& times = hotel_time[hotel_name]; 
    return times.size();
  }

  int Rooms(string &hotel_name){
    deque<int>& rooms = hotel_rooms[hotel_name];
    int total_room = 0;
    for(auto r:rooms){
      total_room += r;
    }
    return total_room;
  }

private:
  map<string,deque<int>> hotel_rooms;
  map<string,deque<int>> hotel_time;
};

第二种实现代码 #

#include <iomanip>
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <utility>
#include <deque>

using namespace std;

class HotelManagement {

public:
  HotelManagement() : current_time(-99999999),hotel_rooms(), hotel_time(){}

  void Book (int &time, string &hotel_name, int &client_id, int &room_count){
    hotel_rooms[hotel_name].push_back(room_count);
    hotel_time[hotel_name].push_back(time);
    current_time = time;
    }

  int Clients(string &hotel_name){
    deque<int>& times = hotel_time[hotel_name]; 
    deque<int>& rooms = hotel_rooms[hotel_name];

    if (times.size() == 0){
      return 0;
    }

    while(times.front() <= current_time - 86400){
      if (!times.empty()){
        times.pop_front();
        rooms.pop_front();
        }
    }
    return times.size();
  }


  int Rooms(string &hotel_name){
    deque<int>& times = hotel_time[hotel_name]; 
    deque<int>& rooms = hotel_rooms[hotel_name];
    
    if (times.size() == 0){
      return 0;
    }

    while(times.front() <= current_time - 86400){
      if (!times.empty()){
        times.pop_front();
        rooms.pop_front();
        }
    }
    
    
    int total_room = 0;
    for(auto r:rooms){
      total_room += r;
    }
    return total_room;
  }

private:
  map<string,deque<int>> hotel_rooms;
  map<string,deque<int>> hotel_time;
  int current_time;
};

主函数代码 #

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  HotelManagement hotel;

  int query_count;
  cin >> query_count;

  for (int query_id = 0; query_id < query_count; ++query_id) {
    string query_type;
    cin >> query_type;

    if (query_type == "BOOK") {
      int time, client_id, room_count;
      string hotel_name;
      cin >> time >> hotel_name >> client_id >> room_count;
      hotel.Book(time, hotel_name, client_id, room_count);
    } else if (query_type == "CLIENTS") {
      string hotel_name;
      cin >> hotel_name;
      cout << hotel.Clients(hotel_name) << "\n";
    } else if (query_type == "ROOMS") {
      string hotel_name;
      cin >> hotel_name;
      cout << hotel.Rooms(hotel_name) << "\n";
    } 
    
  }
  return 0;
}

测试用例 #

输入 #

11
CLIENTS Marriott
ROOMS Marriott
BOOK 10 FourSeasons 1 2
BOOK 10 Marriott 1 1
BOOK 86409 FourSeasons 2 1
CLIENTS FourSeasons
ROOMS FourSeasons
CLIENTS Marriott
BOOK 86410 Marriott 2 10
ROOMS FourSeasons
ROOMS Marriott

输出 #

0
0
2
3
1
1
10

错误信息 #

Failed case #4/17: Wrong answer

(Time used: 0.00/1.00, preprocess time used: 0/None, memory used: 102293504/536870912.)

内容的提问来源于stack exchange，提问作者Daniil Yefimov