(51NOD) 1619. 完全二叉树的方差

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1619

首先，經由證明(?)，一定是a_i中最大的跟b_j中最小，a_i第二大跟b_j第二小配。

知道這個後，要怎麼配呢(?)

我們可以枚舉一個數字X，代表你選的數字要盡量接近這個X。

再亂搞一通(?)後，就AC了(?)。

cal(x) 會回傳一個x節點的二元樹直徑。

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const double eps = 1e-9;

const int N = 1006;

int a[N],b[N];

int cal(int x)
{
    if (x == 1) return 0;
    return floor(log2(x)+eps) + floor( log2( x - pow(2, (int)(floor(log2(x)) + eps)-1 ) ) + eps );
}

int merge_root(int a,int b)
{
    return max( max( cal(a) , cal(b) ),(int)( floor(log2(a)) + floor(log2(b)) ) + 1 );
}

int merge_leaf(int a,int b)
{
    return cal(a) + cal(b) +1;
}

int d[N];

int L[N],R[N];

const LL INF = (1LL<<60);

int _[N];

int n;

LL solve(LL x)
{
    LL sum=0;
    for (int i=1;n>=i;i++)
    {
        if (R[i] < x) _[i] = R[i];
        else if (L[i] > x) _[i] = L[i];
        else _[i] = x;
        sum += _[i];
    }
    LL ret=0;
    for (int i=1;n>=i;i++)
    {
        ret += (n * _[i] - sum) * (n * _[i] - sum);
    }
    return ret;
}

int main ()
{
    scanf("%d",&n);
    for (int i=1;n>=i;i++)
    {
        scanf("%d",&a[i]);
    }
    for (int i=1;n>=i;i++)
    {
        scanf("%d",&b[i]);
    }
    sort(a+1,a+n+1);
    sort(b+1,b+n+1);
    reverse(b+1,b+n+1);
    int mx = -1,mn = (1<<20);
    for (int i=1;n>=i;i++)
    {
        L[i] = merge_root(a[i],b[i]);
        R[i] = merge_leaf(a[i],b[i]);
        mx = max(mx,R[i]);
        mn = min(mn,L[i]);
    }
    LL ans = INF;
    for (int i=mn;mx>=i;i++)
    {
        LL ret = solve(i);
        if (ret < ans) ans = ret;
    }
    printf("%lld\n",ans);
}