CSP-201609-2-火车购票
解题思路
-
初始化座位: 首先，它创建了一个20行5列的二维向量
seatMap用于表示车厢的座位情况。每个座位按顺序赋予了一个编号，从1到100。这部分代码通过两层循环完成，外层循环遍历所有的排，内层循环遍历每一排的座位，并分配座位编号。 -
读取购票指令: 接下来，程序读取第一行输入n，表示有n条购票指令。随后的循环中，每次读取一个数
seatNum，表示当前购票指令要购买的票数。 -
座位分配:
-
优先安排相邻座位: 对于每一条购票指令，程序首先尝试在某一排内找到足够的相邻座位。这通过遍历
seatMap中的每一排来实现。如果找到一个排里有足够的空座位（即该排的座位数不小于seatNum），就输出这排中最前面的seatNum个座位的编号，并从seatMap中移除这些座位，标记本次购票已完成。 -
分散安排座位: 如果没有找到足够的相邻座位，则进入分散安排模式。在这个模式下，程序遍历所有排，依次输出空座位的编号，直到满足购票需求为止。这种情况下，分配的座位可能不是相邻的。
-
座位删除: 对于已经出售的座位，理论上应该从
seatMap中删除这些座位，以防止再次售出。（在分散安排中并没有执行这一删除操作，详见注释）
-
完整代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<vector<int>>seatMap(20, vector<int>(5));
int main() {
int n, seatNum;
cin >> n;
// 座位初始化
int index = 1;
for (auto& it : seatMap) {
for (auto& jt : it) {
jt = index;
index++;
}
}
// 购票
for (int i = 0; i < n; i++)
{
cin >> seatNum;
bool isFinish = 0; // 本次出票是否完成
for (auto& it : seatMap) {
if (it.size() >= seatNum) // 可以安排在同一行
{
for (int j = 0; j < seatNum; j++)
{
cout << it[j] << " ";
}
for (int j = 0; j < seatNum; j++)
{
it.erase(it.begin());
}
isFinish++;
break;
}
}
if (!isFinish) // 没有完成
{
int haveSale = 0; // 当前卖了多少票
bool flag = 0; // 控制外层循环退出
/*
注意：本题的正确思路应当是在每次出票后删除对应座位
这里代码中没有删除的逻辑，因为不删除也能AC,说明不能
连续出票的测试样例在最够一个查询中
*/
for (auto& it : seatMap) {
for (auto& jt : it) {
cout << jt << " ";
haveSale++;
if (haveSale == seatNum) { // 出票完成
flag++;
break;
}
}
if (flag) break;
}
}
cout << endl;
}
return 0;
}
