后三个点超时,求助各位大佬帮忙看看该怎么改?

回复帖子

@星球123 2021-05-04 23:11 回复
#include<bits/stdc++.h>
using namespace std;
int a[1000005];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    cin>>a[i];
    cout<<a[1]<<endl;
    for(int i=2;i+1<=n;i+=2)
    {
        sort(a+1,a+i+2);
        cout<<a[(i+2)/2]<<endl;
    }
    return 0;
}
@lcyxds 2021-05-05 22:04 回复 举报

@星球123 由于你要对 $O(N)$ 个长度为 $O(N)$ 的数组排序,你的时间复杂度是 $\Theta(N^2\log N)$,正解是 $O(NlogN)$,建议你使用树状数组或者 STL 堆来做这题

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。