问题 : 占座位

一时失言乱红尘 2022-06-10 07:15 157阅读 0赞

题目描述  
sun所在学校的教室座位每天都是可以预占的。  
一个人可以去占多个座位，而且一定是要连续的座位，如果占不到他所要求的这么多座位，那么他就一个座位也不要了。为了降低难度，每次分配座位按座位号从小到大查找，采用最先适配法分配座位。  
输入  
输入有多组数据。  
每组数据输入座位排数n，座位的排列数相等，座位是按每行从左到右依次排序的,，第1行的最右边一个座位与第二行的第一个座位视为连续座位），m个人。  
然后输入k，最后输入k个命令。  
命令只有两种：  
1.in id num（代表id,要占num个座位，若占不到连续的num个座位表示该命令无效）  
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

AC代码

#include<iostream>
    #include<vector>
    using namespace std;
    vector<int>v;
    int deal(int x){
        for(int i=0;i<=v.size()-x;i++)
        {
            if(v[i]==0)  
            {
                int j=i;
                for(;j<=i+x-1;j++)
                {
                    if(v[j]!=0)
                        break;
                }
                if(j==i+x)
                    return i;
            }
        }
        return -1;
    }
    int main(){
        int n,m,k,n1,n2,l;
        cin>>n>>m>>k;
        v.resize(n*n);
        string s;
        bool p,q;
        for(int i=0;i<k;i++)
        {
            p=false;
            q=true;
            cin>>s;
            if(s=="in")
            {
                cin>>n1>>n2;
                for(int j=0;j<n*n;j++)
                    if(v[j]==n1)
                    p=true;
                if(p)
                {
                    cout<<"no"<<endl;
                    continue;
                }
                else
                {
                    int x=deal(n2);
    
                    if(x==-1)
                    {
                        cout<<"no"<<endl;
                        continue;
                    }
                    else
                    {
                         cout<<"yes"<<endl;
                         for(int x_=x;x_<=x+n2-1;x_++)
                            v[x_]=n1;
                         continue;
                    }
                }
            }
            else
            {
                cin>>l;
                for(int k=0;k<n*n;k++)
                    if(v[k]==l)
                    v[k]=0;
            }
        }
        return 0;
    }