[PAT-A] 1165 Block Reversing

Java

测试点5超时

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

public class Main {
    static final int N = 100010;

    static int n, k;
    static int head;
    static int[] e = new int[N];
    static int[] ne = new int[N];
    static ArrayList<Integer> list = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] firstLine = br.readLine().split(" ");
        head = Integer.parseInt(firstLine[0]);
        n = Integer.parseInt(firstLine[1]);
        k = Integer.parseInt(firstLine[2]);

        for (int i = 0; i < n; ++i) {
            String[] inputs = br.readLine().split(" ");
            int addr = Integer.parseInt(inputs[0]);
            int data = Integer.parseInt(inputs[1]);
            int next = Integer.parseInt(inputs[2]);
            e[addr] = data;
            ne[addr] = next;
        }

        for (int p = head; p != -1; p = ne[p]) {
            list.add(p);
        }

        for (int i = 0; i < list.size(); i += k) {
            int end = Math.min(i + k, list.size());
            Collections.reverse(list.subList(i, end));
        }

        Collections.reverse(list);

        for (int i = 0; i < list.size() - 1; ++i) {
            System.out.printf("%05d %d %05d\n", list.get(i), e[list.get(i)], list.get(i + 1));
        }
        System.out.printf("%05d %d -1\n", list.get(list.size() - 1), e[list.get(list.size() - 1)]);
    }
}

C++

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

using namespace std;

const int N = 100010;

int n, k;
int head, e[N], ne[N];
vector<int> L;

int main() {
    scanf("%d%d%d", &head, &n, &k);

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

    for (int p = head; p != -1; p = ne[p]) L.push_back(p);

    for (int i = 0; i < L.size(); i += k)
        reverse(L.begin() + i, L.begin() + min(i + k, (int) L.size()));

    reverse(L.begin(), L.end());

    for (int i = 0; i < L.size() - 1; ++i)
        printf("%05d %d %05d\n", L[i], e[L[i]], L[i + 1]);
    printf("%05d %d -1\n", L[L.size() - 1], e[L[L.size() - 1]]);

    return 0;
}