题目解析

这道题的核心在于理解原始输入的结构与拦截后的数据关系。

原输入结构

原始合法输入包含：

• 第一行：两个整数 $n$ 和 $m$（网格大小）
• 接下来 $n$ 行：每行 $m$ 个整数，网格内的数值

因此总共有：

• $2$ 个整数（$n$ 和 $m$）
• $n \times m$ 个整数（网格内的数据）

总整数个数：

问题转化

拦截者将所有这些 $k$ 个整数打乱顺序，全部放在一行。题目保证 $n$ 和 $m$ 本身也在这 $k$ 个整数之中（即 $n$ 和 $m$ 两个值也作为数据出现在输入流中）。

我们已知 $k$ 和打乱后的整数序列，需要恢复任意一组可能的 $(n, m)$。

核心关系

由 $k = n \times m + 2$ 可得：

我们需要在打乱后的整数中，找到两个数 $n$ 和 $m$，使得：

并且 $n$ 和 $m$ 必须在序列中出现至少一次（注意：若 $n = m$，需要出现至少两次）。

解法思路

方法一：计数器法

$1$. 统计每个整数 $x$ 在输入中出现的次数，存入数组 freq[x]。 $2$. 遍历所有可能的 $n$（$1 \leq n \leq k$）：

• 若 $n \times n = k - 2$，检查 $freq[n] >= 2$（因为 $n$ 既作为尺寸值出现，又可能在网格内重复出现，但这里至少需要出现两次）
• 否则，若 $(k-2) \% n == 0$，令 $m = (k-2) / n$，检查 $freq[n] > 0$ 且 $freq[m] > 0$（且 $m$ 在 $[1, k]$ 范围内）

$3$. 输出找到的第一组 $(n, m)$。

时间复杂度：$O(k \log k)$（排序可优化到 $O(k)$，但这里遍历 + 取模可视为 $O(k)$）。

方法二：双指针法

$1$. 对输入数组排序。 $2$. 使用双指针 $l = 0$, $r = k-1$，寻找两个数 $a[l]$ 和 $a[r]$ 满足 $a[l] \times a[r] = k-2$。 3. 注意：$n$ 和 $m$ 都可能等于 $a[l]$ 或 $a[r]$，双指针遍历自然能处理相等情况。

这种方法不需要额外处理 $n=m$ 的边界情况。

代码解析（计数器法）

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int t;
    cin >> t;
    
    while (t--) {
        int k;
        cin >> k;
        
        vector<int> freq(k + 1, 0);
        
        for (int i = 0; i < k; i++) {
            int x;
            cin >> x;
            freq[x]++;
        }
        
        pair<int, int> solution = {-1, -1};
        
        // 遍历可能的 n
        for (int i = 1; i <= k; i++) {
            // 情况1: n == m
            if (i * i == k - 2) {
                if (freq[i] > 1) {
                    solution = {i, i};
                }
            } 
            // 情况2: n != m
            else if ((k - 2) % i == 0) {
                int j = (k - 2) / i;
                if (j >= 1 && j <= k && freq[i] > 0 && freq[j] > 0) {
                    solution = {i, j};
                }
            }
        }
        
        cout << solution.first << " " << solution.second << endl;
    }
    
    return 0;
}

关键细节

• 数组大小设为 $k+1$ 是因为输入值 $a_i \leq k$。
• 检查 $j \geq 1$ 且 $j \leq k$ 防止越界。
• 如果 $i \times i = k-2$，必须保证 $freq[i] > 1$，因为 $n$ 和 $m$ 都需要在序列中出现（至少两个 $i$）。
• 当 $i \neq j$ 时，只需 $freq[i] > 0$ 且 $freq[j] > 0$。

复杂度分析

• 时间复杂度：$O(k)$ 遍历一次统计频率，$O(k)$ 遍历寻找解 → $O(k)$。
• 空间复杂度：$O(k)$ 存储频率数组。

题目提到 $O(k \log k)$ 是因为排序方法，但这里频率数组法更优。

总结

这道题的本质是已知 $k$ 和一组包含 $n$ 和 $m$ 的数值，求 $n \times m = k-2$ 的任意解。利用频率统计可以高效求解，注意 $n=m$ 时的出现次数要求即可。