[PAT] 1052 Linked List Sorting

(重要!)
静态链表

tips

题目可能会有无效结点,即不在题目给出的首地址开始的链表上。因此要先遍历一遍链表,标记出有效结点。
数据里面还有均无效的情况,这时要输出“0 -1”(我想到了这个情况但只输出了0...太无奈了QAQ)

AC代码

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define MAX 100010
struct Node {
    int adress;
    int key;
    int next;
    bool in;
}node[MAX];
bool cmp(Node a, Node b) {
    if (a.in == false || b.in == false)
        return a.in > b.in;
    else return a.key < b.key;
}
int main() {
    int start, n;
    scanf("%d%d", &n, &start);
    for (int i = 0;i < MAX;i++)
        node[i].in = false;
    for (int i = 0;i < n;i++) {
        int ad;
        scanf("%d", &ad);
        node[ad].adress = ad;
        scanf("%d%d",&node[ad].key, &node[ad].next);
    }
    int p = start;
    while (p != -1) {
        node[p].in = true;
        p = node[p].next;
    }
    sort(node, node + MAX, cmp);
    start = node[0].adress;
    n = 0;
    while (node[n].in == true) {
        node[n].next = node[n + 1].adress;
        n++;
    }
    node[n - 1].next = -1;
    printf("%d", n);
    if (n > 0)printf(" %05d\n", start);
    else printf(" -1\n");
    for (int i = 0;i < n;i++) {
        printf("%05d %d ", node[i].adress, node[i].key);
        if (node[i].next == -1)
            printf("-1\n");
        else printf("%05d\n", node[i].next);
    }
    return 0;
}

上一篇:PAT A1052 Linked List Sorting (25 分)——链表,排序


下一篇:PAT 1052 卖个萌