PAT 甲级 A1074 Reversing Linked List (25 分)

题目传送门

我自己搞了几个小时搞出来的23分代码：

#include "bits/stdc++.h"
using namespace std;
struct node{
    int Address,Data,Next;
};
node origin[100100],ans[100100];
void revers(int begin,int K){
    for (int i = begin; i < begin+K/2; ++i) {
        swap(ans[i],ans[2*begin+K-1-i]);
    }
}
int main(){
    int N,K,first;
    cin>>first>>N>>K;
    for (int i = 0; i < N; ++i) {
        int temp;
        scanf("%d",&temp); origin[temp].Address = temp;
        scanf("%d %d",&origin[temp].Data,&origin[temp].Next);
    }
    int cnt = 1;
    ans[0] = origin[first];int tmp = ans[0].Next;
    for (int i = 1; i < N; ++i)
    {
        ans[i] = origin[tmp];
        tmp = ans[i].Next;
    }
    for (int i = 0; i < cnt; ++i) {
        ans[i].Next = ans[i+1].Address;
    }
    for (int i = 0; i < N; ++i) {
        if (ans[i].Next==-1 or ans[i].Data==0) break;
        cnt++;
    }
    for (int j = 0; j < N;) {
        if (j+K<=cnt) {
            revers(j,K);
        }
        j+=K;
    }
    for (int i = 0; i < cnt; ++i) {
        ans[i].Next = ans[i+1].Address;
    }
    for (int i = 0; i < cnt-1; ++i) {
        printf("%05d %d %05d\n",ans[i].Address,ans[i].Data,ans[i].Next);
    }
    printf("%05d %d %d",ans[cnt-1].Address,ans[cnt-1].Data,-1);
}
           

然后反思，其实根本没必要自己写swap来反转，vector里面直接有revers函数…也用不到结构体…

如下：(y总的AC代码)

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 100010;

int n, m;
int h, e[N], ne[N];

int main()
{
    scanf("%d%d%d", &h, &n, &m);

    for (int i = 0; i < n; i ++ )
    {
        int address, data, next;
        scanf("%d%d%d", &address, &data, &next);
        e[address] = data, ne[address] = next;
    }

    vector<int> q;
    for (int i = h; i != -1; i = ne[i]) q.push_back(i);

    for (int i = 0; i + m - 1 < q.size(); i += m)
        reverse(q.begin() + i, q.begin() + i + m);

    for (int i = 0; i < q.size(); i ++ )
    {
        printf("%05d %d ", q[i], e[q[i]]);
        if (i + 1 == q.size()) puts("-1");
        else printf("%05d\n", q[i + 1]);
    }

    return 0;
}
``