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交换，则可以通过j将i与k交换。

使用这些信息，我们可以看到，如果我们可以构造一组索引，使得对于集合中的每个元素i，至少存在一个可以与之交换的元素j ，那么我们可以简单地将这些索引处的值排列在排序顺序，这将是这些索引可能的字典最小排列。如果我们继续考虑所有这样的集合，那么我们最终会得到字典上最小的排列。

看待问题的另一种方法（而不是将这些视为不相交集的集合）是将其视为图形问题。如果每个索引是一个节点和两个索引之间的一条边（如果它们可以交换），那么我们需要找到不同的强连通分量（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 回答