2AC4T蒟蒻求助

Yanran_10086 @ 2023-09-10 09:25:28

#include <bits/stdc++.h>
using namespace std;
template<typename T>
inline void fastscan(T& number) {
    bool negative = false;
    register int c;

    number = 0;
    c = getchar();
    if (c=='-') {
        negative = true;
        c = getchar();
    }
    for (; (c>47 && c<58); c=getchar())
        number = number * 10 + c - 48;
    if (negative)
        number *= -1;
}

template<typename T>
inline void fastprint(T number) {
    if (number < 0) {
        putchar('-');
        number *= -1;
    }
    char buffer[10];
    int length = 0;
    do {
        buffer[length++] = number % 10 + '0';
        number /= 10;
    } while(number);
    for(int i = length - 1; i >= 0; i--)
        putchar(buffer[i]);
}
int main() {
    int n;
    fastscan(n);
    vector<long long> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        if ((i + 1) % 2 != 0) {
            nth_element(a.begin(), a.begin() + i / 2, a.begin() + i + 1);
            fastprint(a[i/2]);
            cout<<endl;
        }
    }
    return 0;
}

by _QyGyQ_ @ 2023-09-10 09:32:29

这代码我看都看不懂 QAQ wu~

by _QyGyQ_ @ 2023-09-10 09:33:55

我用队列做的

#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
using ll=long long;
const int N=1e6+7;
priority_queue<int> q;
priority_queue<int,vector<int>,greater<int>> Q;
int a[N];
vector<int>v;
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        int b;
        cin>>b;
        if(q.empty()||b<q.top()){
            q.push(b);
        }
        else Q.push(b);
        while(q.size()<Q.size()+1){
            q.push(Q.top());
            Q.pop();
        }
        while(q.size()>Q.size()+1){
            Q.push(q.top());
            q.pop();
        }
        if(i&1) cout<<q.top()<<"\n";
    }
    return 0;
}

看下行不行 @KeQingLoveYou

by hzjnsy @ 2023-09-10 09:36:11

复杂度不对。

by Yanran_10086 @ 2023-09-10 09:43:21

@hzjnsy 已经尽力优化过了，使用了快读快出，排序复杂度也是线性的

by Yanran_10086 @ 2023-09-10 09:52:10

@meng_cen 可以了，谢谢，对你的代码进行了一些改进：

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;

    priority_queue<int> maxHeap; 
    priority_queue<int, vector<int>, greater<int>> minHeap;  

    for (int i = 1; i <= n; i++) {
        int b;
        cin >> b;

        if (maxHeap.empty() || b < maxHeap.top()) {
            maxHeap.push(b);
        } else {
            minHeap.push(b);
        }
        if (maxHeap.size() > minHeap.size() + 1) {
            minHeap.push(maxHeap.top());
            maxHeap.pop();
        } else if (maxHeap.size() < minHeap.size()) {
            maxHeap.push(minHeap.top());
            minHeap.pop();
        }

        if (i & 1) {
            cout << maxHeap.top() << "\n";
        }
    }

    return 0;
}

采用了两个堆来维护中位数左右的元素，并根据堆的大小关系进行调整