2014年10月3日 星期五

2014/10/03 TopCoder SRM 627 Div1 500 GraphInversions

/*
    我的寫法是直接做啦
    原本175筆測資 會 TLE 1筆
    後來加了那兩行剪枝 就過了xDDDD

    複雜度 我算不出來._____.

    理論上用BIT做 逆序數對數
    在每次DFS 進入,出去時 
    直接增減當前逆序數對值 會更快
    O(N^2*lgN)
*/
// http://community.topcoder.com/stat?c=problem_statement&pm=13275&rd=16008
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

int N, K;
bool visit[2000];
vector<int> v[2000];
vector<int> val;
const int INF = 2000000000;
int Ans;

int A[2000]; int P[2000]; int C[2000]; int ans = 0;

int ms(int *l, int *r)
{
    if( l+1 == r ) return 0;

    int *m = l+(r-l)/2;
    int re = 0;

    re += ms(l, m);
    if( re >= Ans ) return re;
    re += ms(m, r);
    if( re >= Ans ) return re;

    int *li = l, *mi = m, *ci = C;

    while( li != m && mi != r )
    {
        if( *mi < *li )
        {
            re += m-li;
            *ci = *mi;
            ci++; mi++;
        }
        else
        {
            *ci = *li;
            ci++; li++;
        }
    }

    while( li != m )
    {
        *ci = *li;
        ci++; li++;
    }

    while( mi != r )
    {
        *ci = *mi;
        ci++; mi++;
    }

    li = l; ci = C;

    while( li != r )
    {
        *li = *ci;
        li++; ci++;
    }

    return re;
}

void DFS(int O, int st)
{
    visit[O] = true;
    A[st-1] = val[O];

    if( st == K )
    {
        for(int Ki = 0; Ki < K; Ki++) P[Ki] = A[Ki];
        ans = 0;//merge_sort(P, P+K);
        Ans = min(Ans, ms(P, P+K));
    }
    else
    {
        for(int vi = 0, vn = v[O].size(); vi < vn; vi++)
        {
            int Q = v[O][vi];

            if( !visit[Q] )
            {
                DFS(Q, st+1);
            }
        }
    }

    visit[O] = false;
}

struct GraphInversions
{
    int getMinimumInversions(vector <int> A, vector <int> B, vector <int> _val, int _K)
    {
        for(int i = 0; i < 2000; i++) v[i].clear();

        N = A.size(); K = _K; val = _val;

        for(int Ni = 0; Ni < N; Ni++)
            v[A[Ni] ].push_back(B[Ni] ),
            v[B[Ni] ].push_back(A[Ni] );

        Ans = INF;

        fill(visit, visit+N, false);

        for(int Ni = 0; Ni < N; Ni++)
            DFS(Ni, 1);

        return Ans == INF ? -1 : Ans ;
    }
};

沒有留言:

張貼留言