题意分析

本题要求根据一个由 \(N\) 个二进制位组成的二进制字符串旋转后按字典序排序得到的矩阵的最后一列，找出该矩阵的第一行。

解题思路

1. 观察矩阵性质：
   • 对于一个二进制字符串旋转后排序得到的矩阵，有一个重要性质：矩阵的每一行是原字符串的一个旋转，且排序后矩阵的某一行的最后一位在排序后会成为下一行的第一位。
   • 同时，我们知道矩阵中 \(0\) 和 \(1\) 的个数是固定的，且在排序后，前面若干行以 \(0\) 开头，后面若干行以 \(1\) 开头。
2. 构建辅助数组：
   • 首先统计输入的最后一列中 \(1\) 的个数 \(cnt\)。
   • 构建一个临时数组 tmp，将数组的后 \(cnt\) 个位置置为 \(1\)，其余位置置为 \(0\)。这个数组表示排序后矩阵的第一列。
   • 利用 used 数组标记每个位置是否已经被使用，用于后续匹配过程。
3. 匹配最后一列和第一列：
   • 遍历 tmp 数组，对于每个位置 \(i\)，在最后一列 a 中找到第一个未被使用且值与 tmp[i] 相等的位置 \(j\)，标记该位置已使用，并记录 next[i] = j。next 数组表示排序后矩阵中某一行的最后一位对应下一行的位置。
4. 还原第一行：
   • 从位置 \(0\) 开始，根据 next 数组依次找到每一行的位置，输出对应的值，从而得到排序后矩阵的第一行。

复杂度分析

• 时间复杂度：代码中有几个嵌套的循环。第一个循环用于统计 \(1\) 的个数，时间复杂度为 \(O(N)\)；第二个循环用于初始化 tmp 数组，时间复杂度为 \(O(N)\)；第三个循环用于匹配最后一列和第一列，其中内层的 while 循环在最坏情况下可能会遍历整个最后一列，所以这个循环的时间复杂度为 \(O(N^2)\)；最后一个循环用于还原第一行，时间复杂度为 \(O(N)\)。因此，总的时间复杂度为 \(O(N^2)\)。
• 空间复杂度：使用了几个长度为 \(N\) 的数组，如 a、tmp、next 和 used，所以空间复杂度为 \(O(N)\)。

代码实现

#include <cstdio>
#include <cstring>
using namespace std;  
// 定义数组最大长度
int const MAX = 3005;
// a 数组存储最后一列，tmp 数组存储第一列，next 数组记录位置对应关系
int a[MAX], tmp[MAX], next[MAX];  
// used 数组标记位置是否已使用
bool used[MAX];  

int main()  
{  
    int n, cnt = 0;  
    // 读取二进制位的个数
    scanf("%d", &n);  
    // 初始化 used 数组为 false
    memset(used, false, sizeof(used));  
    // 初始化 tmp 数组为 0
    memset(tmp, 0, sizeof(tmp));  
    // 读取最后一列的二进制位，并统计 1 的个数
    for(int i = 0; i < n; i++)  
    {  
        scanf("%d", &a[i]);  
        if(a[i])  
            cnt++;  
    }  
    // 将 tmp 数组的后 cnt 个位置置为 1
    for(int i = n - cnt; i < n; i++)  
        tmp[i] = 1;  
    // 匹配最后一列和第一列
    for(int i = 0; i < n; i++)  
    {  
        int j = 0;  
        // 找到第一个未使用且值与 tmp[i] 相等的位置
        while(tmp[i] != a[j] || used[j])  
            j++;  
        // 标记该位置已使用
        used[j] = true;  
        // 记录位置对应关系
        next[i] = j;  
    }  
    int ind = 0;  
    // 还原第一行
    for(int i = 0; i < n; i++)  
    {  
        ind = next[ind];  
        if(i != (n - 1))
            printf("%d ", a[ind]);  
        else
            printf("%d\n", a[ind]);
    }  
}