火车票

题目描述

火车票务系统需要处理订单，按照特定规则分配座位。系统需要支持查询余票和订购操作。

算法思路

使用数组模拟座位状态：

1. 用二维数组记录每节车厢每个座位的状态（已售/未售）
2. 订购时按车厢顺序查找能满足连座需求的座位
3. 连座要求可能分布在不同车厢

代码实现

#include <bits/stdc++.h>
using namespace std;
 
int main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    // 每节车厢5个座位，共n节车厢
    vector<vector<int>> seat(n, vector<int>(5, 0)); // 0表示未售
    
    for(int i = 0; i < m; i++){
        int k;
        cin >> k;
        bool sold = false;
        // 尝试在单节车厢内找连续k个座位
        for(int j = 0; j < n && !sold; j++){
            for(int s = 0; s + k <= 5 && !sold; s++){
                bool ok = true;
                for(int t = 0; t < k; t++){
                    if(seat[j][s + t] == 1){
                        ok = false;
                        break;
                    }
                }
                if(ok){
                    // 找到，标记为已售
                    for(int t = 0; t < k; t++){
                        seat[j][s + t] = 1;
                    }
                    cout << j + 1 << "-" << s + 1 << "-" << s + k << endl;
                    sold = true;
                }
            }
        }
        // 如果单节车厢不够，尝试跨车厢
        if(!sold){
            // 收集所有未售座位
            vector<pair<int,int>> available;
            for(int j = 0; j < n; j++){
                for(int s = 0; s < 5; s++){
                    if(seat[j][s] == 0){
                        available.push_back({j, s});
                    }
                }
            }
            if((int)available.size() >= k){
                // 找到k个连续座位（可能跨车厢）
                cout << available[0].first + 1 << "-" << available[0].second + 1;
                for(int t = 1; t < k; t++){
                    cout << " " << available[t].first + 1 << "-" << available[t].second + 1;
                }
                cout << endl;
                for(int t = 0; t < k; t++){
                    seat[available[t].first][available[t].second] = 1;
                }
                sold = true;
            }
        }
        if(!sold){
            cout << "false" << endl;
        }
    }
    return 0;
}

关键点

• 优先在单节车厢内查找连续座位
• 如果单节车厢不够，跨车厢分配
• 使用二维数组模拟座位状态

参考

• CCF-CSP认证