C++14(g++5.4) 解法, 执行用时: 147ms, 内存消耗: 6796K, 提交时间: 2019-10-24 15:36:52

#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
using namespace std;
int n, a[1000001];
int f[1000001];
double g[100001];
void ins(int x){
    while (x <= n)
    {
        f[x] ++;
        x += x & -x;
    }
}
int get(int x) {
    int y = 0;
    while (x) {
        y += f[x];
        x -= x & -x;
    }
    return y;
}
void getg(){
    g[n] = 1e9;
    for (int i = n; i >= 2; i --) {
        int x = floor(g[i] * (i + 1) / (n + 1.));
        if (x >= n) g[i - 1] = (n + 1.) / 2.;
        else
            if (x < 1) g[i - 1] = g[i];
            else
                 g[i - 1] = (double)(g[i] * (i - x)  + x * (x + 1.) / 2. * (n + 1) / (i + 1)) / i;
    }
}
int read(){
    int x =0;
    char c;
    while (!isdigit(c = getchar()));
    do {
        x = x * 10 + c - '0';
    } while(isdigit(c = getchar()));
    return x;
}
int main() {
    int T;
    T = read();
    while (T -- ) {
        n = read();
        for (int i = 1; i <= n ;i ++)
            a[i] = read();
        getg();
        int l = 1;
        while (1) {
            ins(a[l]);
            int x = get(a[l]);
            double v = (double)x * (n + 1) / (l + 1.);
            if (v < g[l]) break;
            ++l;
        }
        for (int i = 1; i <= n; i ++)f[i] = 0;
        printf("%d\n", a[l]);
    }
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 235ms, 内存消耗: 6880K, 提交时间: 2018-11-01 23:09:08

#include<cstdio>
#include<algorithm>
#include<cmath>
#define F double
#define lowbit(x) (x&-x)
using namespace std;
const int N = 100005;

int n,T;
int c[N];
void Add(int x){for(;x<=n;x+=lowbit(x)) c[x]++;return ;}
int Get(int x){int sum=0;for(;x;x-=lowbit(x)) sum+=c[x];return sum;}
int a[N];
F g[N];

int main()
{
	int i,j,k,p;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		for(i=1;i<=n;i++) c[i]=0;
		for(i=1;i<=n;i++)
		    scanf("%d",&a[i]);
		for(g[n]=1e9,i=n-1;i>=1;i--)
		{
			p=floor(g[i+1]*(i+2.0)/(n+1.0));
			if(p<=0) g[i]=g[i+1];
			else if(p>=n) g[i]=(n+1.0)/2.0;
			else g[i]=(F)((n+1.0)*(p+1.0)*p/(i+2.0)/2.0+g[i+1]*(i+1.0-p))/(F)(i+1.0);
		}
		for(i=1;i<=n;i++)
		{
			Add(a[i]); p=Get(a[i]);
			F tmp=(F)p*(n+1.0)/(i+1.0);
			if(tmp<g[i]) break;
		}
		printf("%d\n",a[i]);
	}
	return 0;
}