[PAT-A] 1171 Replacement Selection

Java

测试点3、4、5超时

import java.util.PriorityQueue;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String line;
        while ((line = reader.readLine()) != null) {
            String[] firstLine = line.split(" ");
            int n = Integer.parseInt(firstLine[0]);
            int m = Integer.parseInt(firstLine[1]);

            PriorityQueue<Integer> mem = new PriorityQueue<>();
            PriorityQueue<Integer> tmp = new PriorityQueue<>();

            String[] nums = reader.readLine().split(" ");
            int last = 0;

            for (int i = 1; i <= n; ++i) {
                int x = Integer.parseInt(nums[i - 1]);

                if (i <= m) {
                    mem.add(x);
                    if (i == m) {
                        last = mem.poll();
                        System.out.print(last);
                    }
                } else {
                    if (x < last) {
                        tmp.add(x);
                    } else {
                        mem.add(x);
                    }

                    if (!mem.isEmpty()) {
                        last = mem.poll();
                        System.out.print(" " + last);
                    } else {
                        PriorityQueue<Integer> swap = mem;
                        mem = tmp;
                        tmp = swap;
                        System.out.println();

                        last = mem.poll();
                        System.out.print(last);
                    }
                }
            }

            while (!mem.isEmpty()) {
                System.out.print(" " + mem.poll());
            }

            if (!tmp.isEmpty()) {
                mem = tmp;
                System.out.println();

                boolean isFirst = true;
                while (!mem.isEmpty()) {
                    if (isFirst) {
                        isFirst = false;
                    } else {
                        System.out.print(" ");
                    }
                    System.out.print(mem.poll());
                }
                System.out.println();
            } else {
                System.out.println();
            }
        }
    }
}

C++

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

int n, m;
priority_queue<int, vector<int>, greater<int> > mem, tmp;

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

    int x, last;
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &x);

        if (i <= m) {
            mem.push(x);

            if (i == m) {
                last = mem.top();
                mem.pop();
                printf("%d", last);
            }
        } else {
            if (x < last) tmp.push(x);
            else mem.push(x);

            if (!mem.empty()) {
                last = mem.top();
                mem.pop();
                printf(" ");
                printf("%d", last);
            } else {
                swap(mem, tmp);
                printf("\n");

                last = mem.top();
                mem.pop();
                printf("%d", last);
            }
        }
    }

    while (!mem.empty()) {
        printf(" ");
        printf("%d", mem.top());
        mem.pop();
    }

    if (!tmp.empty()) {
        swap(mem, tmp);
        bool is_first = true;
        printf("\n");

        while (!mem.empty()) {
            if (is_first) is_first = false;
            else printf(" ");
            printf("%d", mem.top());
            mem.pop();
        }
        printf("\n");
    }

    return 0;
}