P4851 破解密码（基础）

解题思路

第一步，理解题意。 密码是八位数字，从生日数字里按规则生成。规则是：先把第 1 个数字删除，再把新的第 1 个数字（也就是原来的第 2 个数字）放到数字序列的末尾。重复这个过程，直到所有数字都被删除。被删除的数字按顺序连起来，就是密码。

第二步，类比排队。 这就像同学们排队做游戏：队伍最前面的人先出列，然后排在第二的人跑到队伍最后面重新排队，接着再让新队首出列……一直重复，直到队伍空了。出列的顺序连起来就是密码。这种"先进先出、队尾插入"的结构，就叫队列（queue）。

第三步，用数组模拟队列。 用一个数组 q 当队列，head 指向队首，tail 指向队尾的下一个空位置。从 head 到 tail 之间的数字，就是当前还在队伍里的数字。

第四步，按规则循环。 每一轮做两件事：先输出 q[head]（第 1 个数字被删除），head 加 1；然后判断队伍里还有没有数字，如果有，就把现在的队首 q[head] 放到队尾 q[tail]，再让 head 和 tail 都加 1。一直循环到 head 等于 tail，说明队伍空了。

第五步，注意边界。 当队伍里只剩最后一个数字时，执行完"删除队首"后队伍就空了，不能再移动数字，所以要用 if (head < tail) 判断一下，防止数组越界。举个例子：输入 20230206，第 1 步删掉 2、把 0 移到末尾，第 2 步删掉 2、把 3 移到末尾……最后被删除的数字依次是 2、2、0、0、0、2、3、6，连起来就是密码 22000236，和样例一致。

参考代码

// 破解密码：每次删第1个、把第2个移到末尾，删掉的数字组成密码
#include <iostream>
using namespace std;
int main() {
    char s[20];
    cin >> s;
    int q[100];        // 队列
    int n = 0;
    while (s[n] != '\0') {  // 把8位数字读入队列
        q[n] = s[n] - '0';
        n++;
    }
    int head = 0, tail = n;
    while (head < tail) {
        cout << q[head];    // 删除第1个数字
        head++;
        if (head < tail) {  // 还有数字，把新第1个移到末尾
            q[tail] = q[head];
            head++;
            tail++;
        }
    }
    cout << endl;
    return 0;
}

复杂度分析

时间复杂度：每个数字只被删除一次、最多被移动一次，所以总操作次数与数字个数成正比，是 O(n)。n=8 是常数，运行非常快。

空间复杂度：队列数组大小固定为 100，是 O(1)。