CCF-CSP-201609-2-火车购票

本文主要是介绍CCF-CSP-201609-2-火车购票，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

问题描述
　　请实现一个铁路购票系统的简单座位分配算法，来处理一节车厢的座位分配。
　　假设一节车厢有20排、每一排5个座位。为方便起见，我们用1到100来给所有的座位编号，第一排是1到5号，第二排是6到10号，依次类推，第20排是96到100号。
　　购票时，一个人可能购一张或多张票，最多不超过5张。如果这几张票可以安排在同一排编号相邻的座位，则应该安排在编号最小的相邻座位。否则应该安排在编号最小的几个空座位中（不考虑是否相邻）。
　　假设初始时车票全部未被购买，现在给了一些购票指令，请你处理这些指令。
输入格式
　　输入的第一行包含一个整数n，表示购票指令的数量。
　　第二行包含n个整数，每个整数p在1到5之间，表示要购入的票数，相邻的两个数之间使用一个空格分隔。
输出格式
　　输出n行，每行对应一条指令的处理结果。
　　对于购票指令p，输出p张车票的编号，按从小到大排序。
样例输入
4
2 5 4 2
样例输出
1 2
6 7 8 9 10
11 12 13 14
3 4
样例说明
　　1) 购2张票，得到座位1、2。
　　2) 购5张票，得到座位6至10。
　　3) 购4张票，得到座位11至14。
　　4) 购2张票，得到座位3、4。
评测用例规模与约定
　　对于所有评测用例，1 ≤ n ≤ 100，所有购票数量之和不超过100。

分析：
1.题目中第2行的每一个输入都<=5，说明每个人的购票数量<=5张；
2.首先需要考虑每一排是否存在空余座位能够容纳当前需要分配的人数，且尽可能同一排座位相邻，实在没有合适的位置才需要不相邻。
3.需要注意，当可以分配座位时，需要更新剩余座位或者是此时剩余人数。

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <stack>
#include <cstring>
#include <math.h>
#define MAX 1100
using namespace std;
// struct Node
// {
//     int w, y;
//     char t;
// } node[MAX];
// struct line
// {
//     int x1, x2, x3;
// } l[20];

int main()
{
    int n;
    cin >> n;
    int a[100];
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    int seats[20][6];
    for (int i = 0; i < 20; i++)
    {
        seats[i][0] = 5; //初始化每一排的剩余座位
    }
    for (int i = 0; i < n; i++)
    {
        bool success = false;
        // int x = a[i];
        for (int j = 0; j < 20; j++)
        {
            int s = seats[j][0];//记录空闲位置
            if (s >= a[i])//空闲位置刚好能够分配
            {
                int start = 5 - s + 1; //开始坐的位置
                seats[i][0] -= a[i];   //从剩余的位置中减去分配的位置
                success = true;        //成功分配
                for (int k = start; k < start + a[i]; k++)
                {
                    int y = j * 5 + k; //记录分配的位置
                    cout << y << " ";  //将位置输出
                }
                cout << endl;
                break;
            }
        }
        if (!success) //没有成功分配
        {
            for (int j = 0; j < 20; j++)
            {
                int s = seats[j][0];
                while (s > 0 && a[i] > 0) //存在空位且人数尚未分配完成
                {
                    int y = j * 5 + 5 - s + 1; //记录分配的位置
                    cout << y << " ";          //将位置输出
                    s -= 1;                    //减少一个位置；
                    a[i] -= 1;                    //人数减少一位
                    seats[i][0] = s;           //更新空余位置
                }
                if (a[i] == 0)//一旦人员分配完成即退出
                {
                    break;
                }
            }
            cout << endl;
        }
        else
        {
            continue;
        }
    }
}

这篇关于CCF-CSP-201609-2-火车购票的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！