急救！！！

P1168 中位数

2166776037yyds @ 2024-08-05 19:27:24

蒟蒻在刷水绿题时暴力、快读快写，但因为gsd（形容词）sort超时、超空间了，怎么办？~~（前提：本蒟蒻只会c++入门知识）~~

#include<bits/stdc++.h>
int in()
{
    int k=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')k=k*10+c-'0',c=getchar();
    return k; // 别忘记标记的负数要乘进去
}
void out(int x)
{
    if(x<0)putchar('-'),x=-x;
    if(x<10)putchar(x+'0');
    else out(x/10),putchar(x%10+'0');
}
long long n,a[114514];
using namespace std;
int main()
{
    n=in();
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<=n;i+=2)
    {
        sort(a,a+i+1);
        out(a[(i+1)/2]);
        cout<<endl;
    }
    return 0;
}

by qazsedcrfvgyhnujijn @ 2024-08-05 19:31:43

老老实实写对顶堆去吧。

by piano_pei @ 2024-08-06 20:33:22

@2166776037yyds 可以用vector维护一个有序序列v，这样直接去v[(i+1)/2-1]就行，每次往v里插入时可以二分找一下插入位置，也就是找最后一项>=A[i]在v中的下标，然后直接插入到v里就行，时间复杂度O(nlog_2n)，二分可以直接用lowerbound和upperbound实现，我反正是手写，可以参考一下我的，记得回关

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
vector<int>v;
inline int bs(int x)
{
    // 求x的插入位置 
    if(!v.size()) return 0;
    if(v[0] > x) return 0;
    int l = 0, r = v.size()-1;
    while(l < r)
    {
        int mid = (l+r+1)>>1;
        if(v[mid] <= x) l = mid;
        else r = mid-1;
    }
    return l+1;
}
int main()
{
    int n, x;
    cin >> n;
    for(int i = 1;i <= n;++i)
    {
        scanf("%d", &x);
        v.insert(v.begin()+bs(x), x);
        if(i & 1) cout << v[v.size()>>1] << "\n";
    }
    return 0;
}

by 2166776037yyds @ 2024-08-06 21:24:07

@pianopei 谢谢你，最近已经在学队列了话说你是砂金厨吗？（本人也玩铁道，是刃、砂金and流萤厨）

by 2166776037yyds @ 2024-08-06 21:24:26

@pianopei 已回关

by piano_pei @ 2024-08-06 21:33:58

@2166776037yyds 我是，但没有:( ,歪了老杨

by 2166776037yyds @ 2024-08-06 21:42:01

@pianopei srds，我有砂金！！！砂金太好用啦（逃）