以下是本人四十分代码

P1168 中位数

Xiao_QianQian @ 2024-10-02 19:46:29

以下是本人40分代码,求调

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }
    priority_queue<int> maxHeap;
    priority_queue<int, vector<int>, greater<int>> minHeap;
    for (int i = 1; i <= (N + 1) / 2; ++i) {
        int elementsToProcess = min(2 * i - 1, N);
        for (int j = 0; j < elementsToProcess; ++j) {
            int num = A[j];
            if (maxHeap.empty() || num <= maxHeap.top()) {
                maxHeap.push(num);
            } else {
                minHeap.push(num);
            }
            if (maxHeap.size() > minHeap.size() + 1) {
                minHeap.push(maxHeap.top());
                maxHeap.pop();
            } else if (minHeap.size() > maxHeap.size()) {
                maxHeap.push(minHeap.top());
                minHeap.pop();
            }
        }
        cout << maxHeap.top() << '\n';
        maxHeap = priority_queue<int>();
        minHeap = priority_queue<int, vector<int>, greater<int>>();
    }
    return 0;
}

—————————测试点信息—————————

Subtask #0\

1

Accepted, 得分 20. 4ms/628.00KB AC\

2

Accepted, 得分 20. 86ms/564.00KB AC\

3

Time Limit Exceeded. 1.20s/880.00KB TLE\

4

Time Limit Exceeded. 1.20s/960.00KB TLE\

5

Time Limit Exceeded. 1.20s/876.00KB TLE

Subtask #1\

6

Time Limit Exceeded. 1.20s/872.00KB TLE

——————————分割线——————————

感谢大佬调教


|