题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
#include <functional>

using namespace std;

int main() {
    int T;
    scanf("%d", &T);
    while(T--) {
        int cas, n;
        int cnt = 0;
        scanf("%d %d", &cas, &n);
        printf("%d %d\n", cas, (n + 1) / 2);
        priority_queue<int, vector<int>, greater<int> > q1;     //小根堆，从小到大，表示后半段
        priority_queue<int> q2;     //大根堆，从大到小，表示前半段
        for(int i = 1; i <= n; i++) {
            int x;
            scanf("%d", &x);
            if(q1.empty()) {
                q1.push(x);
            } else {
                if(x > q1.top()) {
                    q1.push(x);
                } else {
                    q2.push(x);
                }
                if(q1.size() < q2.size()) {
                    q1.push(q2.top());
                    q2.pop();
                }
                if(q1.size() > q2.size() + 1) {
                    q2.push(q1.top());
                    q1.pop();
                }
            }
            if(i & 1) {
                cnt++;
                if(cnt % 10 == 0) {
                    printf("%d\n", q1.top());
                } else {
                    printf("%d ", q1.top());
                }
            }
        }
        if(cnt % 10 != 0) {
            printf("\n");
        }
    }
    return 0;
}