关于算法-数据结构:PAT甲级1042-Shuffling-Machine

7次阅读

共计 1292 个字符,预计需要花费 4 分钟才能阅读完成。

题目粗心:

有 54 张牌,编号为 1~ 54,初始按编号从小到大排列。另外,这些牌按初始排列给定花色,即从左至右别离为 13 张 S、13 张 H、13 张 C、13 张 D、2 张 J,如下所示:

S1, S2.., S13, H1, H2,.., H13, C1, C2,..,CI3, D1, D2,., D13,J1,J2

接下来执行一种操作,这种操作将牌的地位扭转为指定地位。例如有 5 张牌 S3, H5, C1,D13, J2, 而后给定操作序列 {4,2, 5,3,1},因而把 S3 放到 4 号位、把 H5 放到 2 号位、C1 放到 5 号位、D13 放到 3 号位、J2 放到 1 号位,于是就变成了 J2, H5, D13, S3, C1。当初须要将这种操作执行 K 次,求最初的排列后果。例如下面的例子中,如果执行第二次操作,那么序列 J2, H5, D13, S3,C1 就会变成 C1, HS, S3, J2, D13.

算法思路:

题目要求模仿洗牌过程,给定初始牌组为 cards, 起始下标地位从 1 开始,给定洗牌程序 orders,和洗牌次数 K, 要求得出最终洗牌后果。
题目比较简单,就是应用 hash 的思维,咱们每次洗牌就创立一个新的数组 new_cards 暂存最终洗牌后果, 该数组的值取决于 orders 与 cards,
其对应关系为 new_cards[orders[j]] = cards[j]; 在 new_cards 数组求解结束后,将 new_cards 数组赋值给 cards 即可,每次循环执行该过程,直到完结

提交后果:

AC 代码:
#include<cstdio>
#include<string>

using namespace std;

string cards[55]={"","S1","S2","S3","S4","S5","S6","S7","S8","S9","S10","S11","S12","S13","H1","H2","H3","H4","H5","H6","H7","H8","H9","H10","H11","H12","H13","C1","C2","C3","C4","C5","C6","C7","C8","C9","C10","C11","C12","C13","D1","D2","D3","D4","D5","D6","D7","D8","D9","D10","D11","D12","D13","J1","J2"};

int main(){
    int K;// 反复次数
    scanf("%d",&K);
    int orders[55];
    for(int j=1;j<55;++j){scanf("%d",&orders[j]);
    }
    for(int i=0;i<K;++i){string new_cards[55];
        for(int j=1;j<55;++j){new_cards[orders[j]] = cards[j];
        }
        // 将 new_cards 的值赋值给 cards
        for(int j=1;j<55;++j){cards[j] = new_cards[j];
        }
    }
    for(int i=1;i<55;++i){printf("%s",cards[i].c_str());
        if(i<54) printf(" ");
    }
    return 0;
}
正文完
 0