首页 > ACM题库 > 九度OJ > 九度-1334-占座位[模拟]
2014
01-27

九度-1334-占座位[模拟]

题目1334:占座位

题目描述:
sun所在学校的教室座位每天都是可以预占的。
一个人可以去占多个座位,而且一定是要连续的座位,如果占不到他所要求的这么多座位,那么他就一个座位也不要了。为了降低难度,每次分配座位按座位号从小到大查找,采用最先适配法分配座位。
输入:
输入有多组数据。
每组数据输入座位排数n,0<n<=100(座位的排列数相等,座位是按每行从左到右依次排序的),m( 0<m<=min(100,n*n) )个人。
然后输入k(0<k<=100),最后输入k个命令。
命令只有两种:
1.in id num(代表id,0<=id<m,要占num个座位,若占不到连续的num(0<num<=20)个座位表示该命令无效)
2.out id(代表id要释放他之前占的所有座位)
注意:如果id之前占过座还没释放那么之后他的in命令都是无效的,
如果id之前没占过座位那么他的out命令也是无效的。
输出:
对每个in命令输出yes或者no,如果命令有效则输出yes,无效则输出no。
在yes no后面只带有回车,不带其他任何字符。
样例输入:
4 10
9
in 1 7
in 2 3
in 3 3
in 3 3
in 4 3
out 2
in 5 6
out 3
in 5 6
样例输出:
yes
yes
yes
no
yes
no
yes
没那么复杂,不需要用到任何算法,只需要基本的编程功底。但是需要理清逻辑。
注意座位越界问题。
座位头和座位尾不算相连。
#include "stdio.h"
#include <string> 
#include "string.h"

struct Node 
{
    Node() 
    {
        beginNum = -1;
        count = 0;
    }
    int beginNum;
    int count;
};

int main() 
{
    int n, m, k, id, num;
    char order[4];
    while (scanf("%d%d%d", &n, &m, &k) != EOF) 
    {
        bool Seat[10000] = { false };
        Node node[100];
        int cnt = n * n;
        for (int p = 0; p < k; p++) 
        {
            scanf("%s%d", order, &id);
            if (strcmp(order,"in") == 0) 
            {
                scanf("%d", &num);
                if (node[id].count > 0 || num > cnt) 
                {
                    printf("no\n");
                    continue;
                }
                //找有没有连续的空座位。
                bool flg;
                int i = num-1, j, beginIndex;
                while(i < cnt)
                {
                    flg = true;
                    for(j = i; j >= i-num+1; j--)
                    {
                        if(Seat[j])
                        {
                            flg = false;
                            break;
                        }
                    }
                    if(flg)
                    {
                        beginIndex = j + 1;
                        break;
                    }
                    else
                    {
                        i = j + num;
                    }
                }
                if (flg) 
                {
                    node[id].beginNum = beginIndex;
                    node[id].count = num;
                    for (j = beginIndex; j < beginIndex + num; j++) 
                    {
                        Seat[j] = true;
                    }
                    printf("yes\n");
                } 
                else 
                {
                    printf("no\n");
                }
            } 
            else
            {
                if (node[id].count == 0) continue;
                for (int i = node[id].beginNum; i < node[id].beginNum + node[id].count; i++) 
                {
                    Seat[i] = false;
                }
                node[id].count = 0;
            }
        }
    }
    return 0;
}

 


  1. a是根先忽略掉,递归子树。剩下前缀bejkcfghid和后缀jkebfghicd,分拆的原则的是每个子树前缀和后缀的节点个数是一样的,根节点出现在前缀的第一个,后缀的最后一个。根节点b出现后缀的第四个位置,则第一部分为四个节点,前缀bejk,后缀jkeb,剩下的c出现在后缀的倒数第2个,就划分为cfghi和 fghic,第3部分就为c、c