洛谷题解 P1160 【队列安排】

题目链接

这道题做的真是曲折

看到题后首先想到的就是链表,既然要插前和插后,那么肯定是要用双向链表

于是我们用结构体定义一个链表的节点

struct queue
{
	int id;
    queue *nxt,*pre;
};

然后我们定义一个头指针,他不是真正的第一位,只是一个起始节点而已

queue *head = (queue *)malloc(sizeof (queue));
head->id=1;
head->nxt = head->pre = NULL;
//head指针应该是个全局变量
//初始化很重要

开局malloc一个head,剩下的全靠插 ,开始插入剩下的节点

for (int i = 2; i <= n; i++)
{
	int k, p; 
	scanf("%d %d", &k, &p);
	updata(k, p, i); 
}
void updata(int k, int p, int i)
{
    queue *now = head; //从头开始找

    while (now->id != k && now->nxt != NULL)
        now = now->nxt; //先向前找
    if (now->id != k) //没找到就向后找
    {
        now = head;
        while (now->id != k && now->pre != NULL)
            now = now->pre;
    }
    queue *q = (queue*)malloc(sizeof(queue));
    q->id = i;
    q->pre = q->nxt = NULL;
    if (p == 0) //插在前面
    {

        if (now->pre == NULL)
        {
            now->pre = q;
            q->nxt = now;
        }
        else
        {
            queue *t = now->pre;
            t->nxt = q;
            q->pre = t;
            now->pre = q;
            q->nxt = now;
        }
    }

    else if (p == 1) //后面
    {
        if (now->nxt == NULL)
        {
            now->nxt = q;
            q->pre = now;
        }

        else
        {
            queue *t = now->nxt;
            t->pre = q;
            q->nxt = t;
            now->nxt = q;
            q->pre = now;
        }
    }
}

接下来我们删掉其中的元素

void outdata(int x)
{
    queue *now = head; //下面还是查找
    while (now->id != x && now->nxt != NULL)
        now = now->nxt;
    if (now->id != x)
    {
        now = head;
        while (now->id != x && now->pre != NULL)
            now = now->pre;
    }
    if (now->id != x)//没找到说明已经删掉了
        return; //以下是分类讨论
    if (now->pre != NULL && now->nxt != NULL)
    {
        now->pre->nxt = now->nxt;
        now->nxt->pre = now->pre;
    }
    else if (now->pre == NULL && now->nxt != NULL)
    {
        now->nxt->pre = NULL;
    }
    else if (now->pre != NULL && now->nxt == NULL)
        now->pre->nxt = NULL;

    else
    {
        now = NULL;
    }
}

对于指针链表的插入删除,要注意细节问题,稍有不慎就会Segmentation fault,还有一点要注意,不要使用clang

我vscode使用clang++编译,程序完美运行,上洛谷后RE,用g++编译后果然有问题 >_<


于是我们就上了完整TLE代码

#include <cstdio>
#include <cstdlib>
#include <iostream>
using namespace std;
int n, m;
struct queue
{
    int id;
    queue *nxt = NULL, *pre = NULL;
} *head = NULL;
void updata(int k, int p, int i)
{
    queue *now = head;

    while (now->id != k && now->nxt != NULL)
        now = now->nxt;
    if (now->id != k)
    {
        now = head;
        while (now->id != k && now->pre != NULL)
            now = now->pre;
    }
    queue *q = (queue *)malloc(sizeof(queue));
    q->id = i;
    q->pre = q->nxt = NULL;
    if (p == 0)
    {

        if (now->pre == NULL)
        {
            now->pre = q;
            q->nxt = now;
        }
        else
        {
            queue *t = now->pre;
            t->nxt = q;
            q->pre = t;
            now->pre = q;
            q->nxt = now;
        }
    }

    else if (p == 1)
    {
        if (now->nxt == NULL)
        {
            now->nxt = q;
            q->pre = now;
        }

        else
        {
            queue *t = now->nxt;
            t->pre = q;
            q->nxt = t;
            now->nxt = q;
            q->pre = now;
        }
    }
}
void outdata(int x)
{
    queue *now = head;
    while (now->id != x && now->nxt != NULL)
        now = now->nxt;
    if (now->id != x)
    {
        now = head;
        while (now->id != x && now->pre != NULL)
            now = now->pre;
    }
    if (now->id != x)
        return;
    if (now->pre != NULL && now->nxt != NULL)
    {
        now->pre->nxt = now->nxt;
        now->nxt->pre = now->pre;
    }
    else if (now->pre == NULL && now->nxt != NULL)
    {
        now->nxt->pre = NULL;
    }
    else if (now->pre != NULL && now->nxt == NULL)
        now->pre->nxt = NULL;

    else
    {
        now = NULL;
    }
}
int main()
{
    scanf("%d", &n);
    head = (queue *)malloc(sizeof(queue));
    head->id = 1;
    head->pre = head->nxt = NULL;
    for (int i = 2; i <= n; i++)
    {
        int k, p;
        scanf("%d %d", &k, &p);
        updata(k, p, i);
    }
    scanf("%d", &m);
    for (int i = 1; i <= m; i++)
    {
        int x;
        scanf("%d", &x);
        outdata(x);
    }
    queue *now = head;
    while (now->pre != NULL)
        now = now->pre;
    while (now->nxt != NULL)
    {
        printf("%d ", now->id);
        now = now->nxt;
    }
    printf("%d", now->id);
    return 0;
}

提交后发现只有40分,后面三个点都TLE了,想想我们的查找操作,每次需要从head向前向后去寻找,时间复杂度爆炸


开始优化,因为每次插入元素不会出现重复,所以我们直接用结构体数组来表示每个节点

struct queue
{
    int pre, nxt;
} q[100010];

下标就是编号,这样我们可以直接找到每个点,时间复杂度O(1)

下面是AC代码

#include <cstdio>
struct queue
{
    int pre, nxt;
} q[100010];
int n, m;
void updata(int k, int p, int i)
{
    if (p == 0)
    {
        int t = q[k].pre;
        q[i].pre = t;
        q[i].nxt = k;
        q[k].pre = i;
        q[t].nxt = i;
    }

    else
    {
        int t = q[k].nxt;
        q[i].nxt = t;
        q[t].pre = i;
        q[k].nxt = i;
        q[i].pre = k;
    }
}
void outdata(int x)
{
    if (q[x].pre != -1) //如果pre为-1的话,说明已经被删掉了
    {
        q[q[x].pre].nxt = q[x].nxt;
        q[q[x].nxt].pre = q[x].pre;
        q[x].pre = -1;
    }
}
int main()
{
    scanf("%d", &n);
    q[1].nxt = -1; //初始化很重要
    q[1].pre = 0;
    q[0].nxt = 1; //q[0]代表第一个节点的左边空位
    q[0].pre = -1;
    for (int i = 2; i <= n; i++)
    {
        int k, p;
        scanf("%d %d", &k, &p);
        updata(k, p, i);
    }
    scanf("%d", &m);
    for (int i = 1; i <= m; i++)
    {
        int x;
        scanf("%d", &x);
        outdata(x);
    }
    for (int i = q[0].nxt; i != -1; i = q[i].nxt)
    {
        printf("%d ", i);
    }
    return 0;
}

AC !


这题做完我就改名 Segmentation_fault了

不要问我为什么>_<