医疗调度系统题解

友利奈绪 edited 3 年，9 月前

本题要求对国民进行排序，但国民的上限十分大（测试样例中甚至达到10 亿）。
因此，在国民人数特别多时，对每个国民都申请存储空间是不现实的，它会导致memory limit exceed。

所以，我们要从另一个变量指令数出发。

可以看到，我们的最大指令数为1000。就特殊情况而言，最多可以对1000个国民进行医疗操作（N*1000）。
显然，指令数的特殊性是我们解题的关键。

睿智的杨老师的解法。（强）

1.先申请3000个单位的连续内存。
2.前2000个空间中从1000 + 1 ~ 2000储存1 ~ 1000位国民的编号，指针head指向第1000 + 1位。前面1000位不放元素是为了emergency极限情况准备空间。
3.后1000个储存经过治疗后的国民的编号。指针rear指向第2000 + 1位。

具体操作如下：

将国民编号放入1001~2000，不满置0。

在遇到指令N时，将head存入输出，同时存入rear所指位置，rear++。head置0，head+k下移至不为0的单位（k > 0）。

在遇到命令E x时。自head向下搜索至3n，若某位置值为x，将此位置值置0，head–上移，x存入head所指。若未找到，那么x必定大于目前等待的人的编号，直接head++上移并存入。

纯手打。

点赞，关注，投喂。（doge）

ps：博主自己的方法就不分享了，思想类似，节省了内存但是时间复杂度增加了，并且有点绕。
哭哭

若文章有问题或有更好想法可发布在评论区或私下联系
邮箱：10204507414@ecnu.edu.cn

2 0

爱吃烤肉的派大星

3 年，9 月前

include

using namespace std;

int main()
{
char cmd;
int people=0,no=0,elem=0,ansno=0;//people为国民人数 no为执行命令的数量 ansno为需要输出样例答案的数量
int casek=1;
while(cin>>people>>no)
{
int Queue[3000]={0};
int front=0,rear=0;
int counter=0;
if(people==0&&no==0){break;}
cout<<”Case “<<casek<<”:”<<endl;

    for(int i=0;i<min(people,no);i++)
    {
        Queue[1000+i]=i+1;
        rear=1001+i;
    }//rear指向实际队列队尾元素的下一个
    front=1000;
    for(int i=0;i<no;i++)
    {
        cin>>cmd;
        if(cmd=='N')//如果N则从队头开始遍历找到第一个不为0的元素并存储答案然后将其移到队尾
        {

            while(Queue[front]==0){front++;}
                cout<<Queue[front]<<endl;
                Queue[rear++]=Queue[front];
                Queue[front++]=0;
        }
        else if(cmd=='E')
        {
            cin>>elem;
            for (int j=front;j<rear;j++)
            {
                if(Queue[j]==elem) Queue[j]=0;
            }
            Queue[--front]=elem;
        }
    }
    casek++;
}

}

回复 2 0

kitten00owner

3 年，9 月前

好得很

回复 1 0

友利奈绪

3 年，9 月前

有位大佬在E x（x为一个极大数， x > n)时，将判断条件设置为 x > n 就直接插入。
这样就导致了在 E x1 ，E x2 （x1 == x2）时会将两个同样的数插入。
所以避免重复的方法最好还是对head以下的进行一次遍历判断。

大佬在很久很久后才发现问题，不说了，帮有点bk的大佬打代码去了。

回复 0 0

友利奈绪

3 年，9 月前

目前帮大佬改正了错误，但任然是wrong answer
代码贴上来，有大佬能看看么。哭哭

include

using namespace std;

int main()
{

int people=0,no=0,elem=0,ansno=0;//people为队列中元素的个数 no为执行命令的数量 ansno为需要输出答案的编号
int front=0,rear=0;
vector<int> answer;//存储所有答案
int contain[10]={0};//存储每一个用例中需要输出元素的个数
int t=0;
//memset(Queue,0,sizeof(int));
//memset(contain,0,sizeof(int));
while(cin>>people>>no)
{
    int Queue[3000]={0};
    int counter=0;
    if(people==0||no==0){break;}
    for(int i=0;i<min(people,no);i++)
    {
        Queue[1000+i]=i+1;
        rear=1001+i;
    }
    front=1000;
    for(int i=0;i<no;i++)
    {
        char cmd;
        cin>>cmd;
        if(cmd=='N')
        {
            counter++;
            while(Queue[front]==0){front++;}
                int temp=Queue[front];
                Queue[front]=0;
                front++;
                Queue[rear]=temp;
                rear++;
                answer.push_back(temp);
        }
        else if(cmd=='E')
        {
            cin>>elem;
                bool judge = false;
                int tar;
                for(int i = front; i < 3001; i++)
                {
                    if(Queue[i]  == elem)
                    {
                        judge = true;
                        tar = i;
                        break;
                    }
                }
                if(!judge) {front--;Queue[front]=elem;}
                else
                {
                    Queue[tar]=0;
                    front--;
                    Queue[front]=elem;

                }
        }
    }
    ansno++;
    contain[t]=counter;
    t++;
}

int j=0;
int i=0;
for(int k=1;k<=ansno;k++)
{

     int check=j;
    cout<<"Case "<<k<<':'<<endl;
    for(j;j<check+contain[i];j++)
    {
        cout<<answer[j]<<endl;
    }
    i++;
    check=j;

}
return 0;

}

回复 3 0

Comments

include

include

include

include

include

服务

开源

关于我们