【CSP试题回顾】201609-2-火车购票

CSP-201609-2-火车购票

解题思路

1. 初始化座位映射：程序首先创建了一个20x5的二维数组setMap来表示车厢的座位分布，每一排有5个座位，总共20排。使用结构体MySet来表示每个座位，其中index字段代表座位编号，而empty字段表示该座位是否已经售出（0代表未售出，1代表已售出）。初始化过程中，将所有座位标记为未售出，并按照从1到100的顺序分配座位编号。

2. 处理购票指令：程序接着读入一个整数n，表示有n条购票指令。然后对每一条指令进行处理，每个指令包含一个整数t，表示需要购买的票数。

3. 查找连续空座：对于每个购票指令，程序首先尝试在车厢中找到连续的t个空座位（未售出）。这是通过遍历每一排座位并统计连续未售出座位的数量来实现的。如果找到足够的连续空座，就将这些座位标记为已售出，并打印出这些座位的编号。

4. 分配非连续座位：如果没有找到足够的连续空座，算法将转而在车厢中寻找任何未售出的座位，直到满足购票数量t。找到后，也将这些座位标记为已售出，并打印出座位的编号。

5. 打印座位编号：无论是找到连续的座位还是非连续的座位，程序都会打印出被分配的座位的编号，并且每条指令处理完毕后都会换行。

完整代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct MySet
{
	int index;
	bool empty; // 0-未售 1-已售
};

vector<vector<MySet>>setMap(20, vector<MySet>(5));
int n,t, setI = 1;

int main() {
	for (auto& it : setMap) {
		for (auto& jt : it) {
			jt.index = setI, jt.empty = 0;
			setI++;
		}
	}
	cin >> n;
	for (size_t i = 0; i < n; i++)
	{
		cin >> t;
		bool canSell = 0; // 是否连续的票可以售出
		for (size_t i1 = 0; i1 < setMap.size(); i1++)
		{
			int emptySet = 0;
			for (size_t i2 = 0; i2 < setMap[i1].size(); i2++) // 查找是否有空座
			{
				if (!setMap[i1][i2].empty) emptySet++;
				if (emptySet == t) {
					canSell = 1;
					break;
				}
			}
			if (canSell) // 开始收票
			{
				for (size_t i2 = 0, i3 = 0; i2 < setMap[i1].size(); i2++)
				{
					if (!setMap[i1][i2].empty) {
						cout << setMap[i1][i2].index << " ";
						setMap[i1][i2].empty = !setMap[i1][i2].empty;
						i3++;
					}
					if (i3 == t)break;
				}
			}
			if (canSell) {
				cout << endl;
				break;
			}
		}
		if (!canSell) // 没有连续的票可以出售
		{
			int sellCount = 0;
			for (auto& it : setMap) {
				for (auto& jt : it) {
					if (!jt.empty)
					{
						cout << jt.index << " ";
						jt.empty = !jt.empty;
						sellCount++;
					}
					if (sellCount == t)break;
				}
				if (sellCount == t)break;
			}
			cout << endl;
		}
	}
	return 0;
}