Lucky Sorting(CodeForces-109D)【思维】

题意：给出一组数，要求从小到大排序，并且排序的过程中，发生交换的两个数至少一个为幸运数（十进制位均为4或7），问能否在（2×n）次交换内完成排序，如果能，输出交换的方案（不要求步骤数最少）。

思路：首先分为两种情况：

　　　　1.所有的数均不为幸运数，则如果给出的序列已经排好序，答案为0,如果未排好序，则无法完成排序。

　　　　2.存在幸运数，可得，只要存在幸运数，就一定能在2×n次以内完成排序。

　　　　　　<1>具体的处理方法是将序列分为若干个闭环，闭环的意思可以举个例子来看，（xio表示下标为xi的元素排序后所在位置下标）,如：x1->x2->x3->x1，这就是一个闭环，表示x1o==x2,x2o=x3,x3o=x1;

　　　　　　<2>首先，一组数在上述规则下一定能分为若干闭环。

　　　　　　<3>分完闭环后，正式进行交换，并且，确定一个幸运数作为操作数（需要且只需要一个），记录其所在闭环

　　　　　　　　3.1首先，将操作数所在闭环进行排序（只需相邻之间两两交换即可，具体可参照上文对于闭环的定义）。

　　　　　　　　3.2再借助操作数对剩余闭环依次排序。第一步为将操作数与待排序闭环中的任意元素交换，再用3.1中的方法操作，最后将操作数归位即可。

　　　　　　　　3.3很容易证明，上述交换操作的总复杂度一定小于2×n.

代码如下：

#include <cstdio>

#include <iostream>

#include <queue>

#include <algorithm>

#include <cstring>

using namespace std;

typedef pair<int, int> P;

int n, arr[], inde[];

bool judge(int x)

{

    while (x != )

    {

        if (x %  !=  && x %  != )

            return false;

        x /= ;

    }

    return true;

}

bool cmp(int a, int b)

{

    return arr[a] < arr[b];

}

int main()

{

    int px = ;

    scanf("%d", &n);

    for (int i = ; i <= n; i++)

        inde[i] = i;

    for (int i = ; i <= n; i++)

    {

        scanf("%d", &arr[i]);

        if (!px && judge(arr[i]))

            px = i;

    }

    sort(inde + , inde +  + n, cmp);

    int iinde[];

    for (int i = ; i <= n; i++)

    {

        iinde[inde[i]] = i;

    }

    if (!px)

    {

        int tans = ;

        for (int i = ; i <= n; i++)

            if (inde[i] != i)

            {

                tans = -;

                break;

            }

        printf("%d", tans);

    }

    else

    {

        vector<P> ans;

        int book[] = {};

        vector<int> aha[];

        int numAha[] = {}, rd = , fgp;

        for (int i = ; i <= n; i++)

        {

            if (book[i])

                continue;

            rd++;

            int p = i;

            while (!book[p])

            {

                book[p] = ;

                aha[rd].push_back(p);

                if (p == px)

                    fgp = rd;

                p = inde[p];

            }

        }

        //flagRound

        memset(book, , sizeof(book));

        if (aha[fgp].size() > )

        {

            int ic = px;

            while (!book[inde[ic]])

            {

                book[ic] = ;

                ans.push_back(P(ic, inde[ic]));

                ic = inde[ic];

            }

        }

        //restRound

        for (int i = ; i <= rd; i++)

        {

            if (i == fgp || aha[i].size() == )

                continue;

            int ic = aha[i][];

            ans.push_back(P(iinde[px], ic));

            while (!book[inde[ic]])

            {

                book[ic] = ;

                ans.push_back(P(ic, inde[ic]));

                ic = inde[ic];

            }

            ans.push_back(P(iinde[px], iinde[aha[i][]]));

        }

        printf("%d\n", ans.size());

        for (int i = ; i < ans.size(); i++)

        {

            printf("%d %d\n", ans[i].first, ans[i].second);

        }

    }

    return ;

}

By xxmlala

巴特西

Lucky Sorting(CodeForces-109D)【思维】

最新文章

热门文章