2

ここに私が取り組んでいる質問があります。私はたくさん試しましたが、O(n^2)より良くなることはできません。

 You are given a set of numbers from 1 to K.And you need to find 
 the minimum possible lexicographical set of numbers with following
 constraints.You are given K numbers of sets of Yes 'Y' or NO 'N' from
 1 to K.And the swap is only possible if the value is 'Y'.Sorry for my
 poor English.Hope this example helps get you the problem. 
 NOTE: 1 < K < 101
 Take an example:
 K=3
Given set of numbers is :  3 1 2
                           N N Y
                           N N N
                           Y N N
     Here you can swap j and i+2 element since the value is Y.

Thus,the output would be   2 1 3

おそらく複雑さの低い、これよりも優れたアプローチを誰かが提案できますか?

ありがとう。

4

2 に答える 2

2

スワップ可能な要素によって与えられる行列を考えてみてください。arr[i][j] が i を j と交換できるかどうかを示す要素を表している場合、

arr[i][j] = arr[j][i] ; for all i, j pairs

また、iが j と交換でき、jがkと交換できる場合、 iとkをjで交換できます。

この情報を使用すると、セット内の各要素iに対して、交換可能な要素jが少なくとも 1 つ存在するようなインデックスのセットを構築できれば、これらのインデックスで値を単純に配置できることがわかります。並べ替えられた順序であり、これらのインデックスで可能な辞書編集上の最小の配置になります。そのようなすべてのセットを検討し続けると、辞書編集的に最小の配置になります。

この問題を (互いに素な集合の集まりとして見るのではなく) 別の見方として、これをグラフの問題として見ることです。各インデックスがノードであり、2 つのインデックス間のエッジが交換可能な場合、異なる強結合コンポーネント(SCC) を見つけて、そのような各コンポーネント内の要素を並べ替える必要があります。これは明らかです。強く接続されたコンポーネントのインデックスは、このコンポーネントの外側の位置と交換できないため、各 SCC を単独で並べ替えて、目的の結果を得ることができます。

この質問はCodeSprint3でも尋ねられましたが、同じことに対する私の解決策は次のとおりです:- 

#include <iostream>
#include <algorithm>
#include <set>
#include <queue>
#include <cstring>


using namespace std;

void sccSetInsertions (set<int>& indexSet, set<int>& valSet, const int& i, const int& val)
{
    indexSet.insert (i);
    valSet.insert(val);
}

void checkSCCMembers(const int& i, const int& k, int *arr, int *swaps, queue<int>& bfsQ,
                     set<int>& sccVals, set<int>& sccIndices, int *considered)
{
    for (int j = 0; j < k; j++)
    {
        if (swaps[j] == 1)
        {
            if (considered[j] == 0)
            {
                bfsQ.push(j);
                sccSetInsertions(sccIndices, sccVals, j, arr[j]);
                considered[j] = 1;
            }           
        }
    }
}

int main (void)
{
    int k, i, j;    
    cin >> k;   
    int arr[k];
    int swaps[k][k];

    for(i = 0; i < k; i++)
    {
        cin >> arr[i];
    }

    char c;    
    for(i = 0; i < k; i++)
    {
        for (j = 0; j < k; j++)
        {
            cin >> c; 
            swaps[i][j] = (c == 'Y');
        }   
    }


    set<int> sccIndices, sccVals;
    queue<int> bfsQ;        
    int considered[k], tmp;

    bzero (considered, sizeof(int) * k);

    for (i = 0; i < k; i++)
    {   
        if (considered[i] == 1)
            continue;
        else
        {

            sccSetInsertions(sccIndices, sccVals, i, arr[i]);
            considered[i] = 1;            
        }
        checkSCCMembers (i, k, arr, swaps[i], bfsQ, sccVals, sccIndices, considered);
        while (bfsQ.size() > 0)
        {
            tmp = bfsQ.front();
            bfsQ.pop();            
            checkSCCMembers(tmp, k, arr, swaps[tmp], bfsQ, sccVals, sccIndices, considered);
        }

        set<int>::iterator itVal = sccVals.begin(), itIndex = sccIndices.begin();
        for(; itIndex != sccIndices.end(); itIndex++, itVal++)
        {
            arr[*itIndex] = *itVal;        
        }
        sccIndices.clear();
        sccVals.clear();
    }

    for (i = 0; i < k; i++)
    {
        cout << arr[i];
        if (i != k - 1)
            cout << " ";
    }
    cout << endl;

    return 0;
}
于 2012-10-29T18:26:50.393 に答える
1

任意のソート アルゴリズムを使用できます。スワップを制限するだけです。そのため、QuickSort、HeapSort などを使用して、制約O(nlgn)を交換する複雑さを軽減できます。

于 2012-07-26T09:21:14.533 に答える