题解

1 条题解

  • 1
    @ 2017-10-07 13:27:41

    本体让求第K大的答案,于是80%为二分答案,首先个时间复杂度加上一个logn。应该只能用O(logn * n)的时间复杂。首先二分答案,求当每一个数为中位数的时候的区间总数。首先每次枚举区间中有那些数大于它就赋值为1,否则赋值为-1.用树状数组或前缀和来维护区间,求大小为零的区间。相当与求顺序对的数量,即可用log的级别来求了。
    #include<iostream>
    #include<algorithm>
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<cstdlib>
    using namespace std;
    typedef long long ll;
    typedef long double ld;
    typedef pair<int,int> pr;
    const double pi=acos(-1);
    #define rep(i,a,n) for(int i=a;i<=n;i++)
    #define per(i,n,a) for(int i=n;i>=a;i--)
    #define Rep(i,u) for(int i=head[u];i;i=Next[i])
    #define clr(a) memset(a,0,sizeof a)
    #define pb push_back
    #define mp make_pair
    #define fi first
    #define sc second
    ld eps=1e-9;
    ll pp=1000000007;
    ll mo(ll a,ll pp){if(a>=0 && a<pp)return a;a%=pp;if(a<0)a+=pp;return a;}
    ll powmod(ll a,ll b,ll pp){ll ans=1;for(;b;b>>=1,a=mo(a*a,pp))if(b&1)ans=mo(ans*a,pp);return ans;}
    ll read(){
    ll ans=0;
    char last=' ',ch=getchar();
    while(ch<'0' || ch>'9')last=ch,ch=getchar();
    while(ch>='0' && ch<='9')ans=ans*10+ch-'0',ch=getchar();
    if(last=='-')ans=-ans;
    return ans;
    }
    //head
    #define N 110000
    int a[N],b[N],c[N],d[N],e[N],n,m;
    ll k;
    int lowbit(int x){
    return x&(-x);
    }
    int bin(int k){
    int l=1,r=m;
    while(l<r){
    int mid=(l+r)/2;
    if(k<=d[mid])r=mid;
    else l=mid+1;
    }
    return l;
    }
    void add(int x){
    for(;x<=m;x+=lowbit(x))e[x]++;
    }
    int find(int x){
    int ans=0;
    for(;x;x-=lowbit(x))ans+=e[x];
    return ans;
    }
    ll check(int k){
    c[0]=0;
    rep(i,1,n)c[i]=c[i-1]+(a[i]>=k);
    rep(i,0,n)c[i]=c[i]*2-i,d[i+1]=c[i];
    sort(d+1,d+n+2);
    d[0]=1;
    rep(i,2,n+1)
    if(d[i]!=d[d[0]])d[++d[0]]=d[i];
    m=d[0];
    ll ans=0;
    rep(i,0,n)c[i]=bin(c[i]);
    rep(i,0,m)e[i]=0;
    rep(i,0,n)
    if(i&1)add(c[i]);
    else ans+=find(c[i]-1);
    rep(i,0,m)e[i]=0;
    rep(i,0,n)
    if((i&1)==0)add(c[i]);
    else ans+=find(c[i]-1);
    return ans;
    }
    int main(){
    n=read();k=read();
    rep(i,1,n)a[i]=read(),b[i]=a[i];
    sort(b+1,b+n+1);
    b[0]=1;
    rep(i,2,n)
    if(b[i]!=b[b[0]])b[++b[0]]=b[i];
    int l=1,r=b[0];
    while(l<r){
    int mid=(l+r)/2+1;
    ll tt=check(b[mid]);
    if(tt==k){
    cout<<b[mid]<<endl;
    return 0;
    }
    if(check(b[mid])>k)l=mid;
    else r=mid-1;
    }
    cout<<b[l]<<endl;
    return 0;
    }

  • 1

信息

难度
9
分类
(无)
标签
(无)
递交数
4
已通过
1
通过率
25%
上传者