题解：视频监控画面紧凑度优化

问题分析

本题要求通过「左、右、上、下」按钮调整网格中画面的位置，使包含所有画面的最小子矩形（紧凑度）面积最小，并计算达到该紧凑度所需的最少按钮按压次数。核心要点：

1. 按钮操作本质是对行或列进行循环移位（环形结构）。
2. 紧凑度由行方向最小覆盖长度和列方向最小覆盖长度的乘积决定。
3. 最少操作次数是行和列各自最优移位次数的总和。

关键思路

1. 环形结构转化为线性问题：

   • 对于行（或列）坐标，排序后通过计算相邻元素的间隔，找到最大间隔。最小覆盖长度 = 总行（列）长 - 最大间隔。
   • 例如，若列坐标排序后为 [2,5,7]，总列长 10，相邻间隔为 3（5-2）、2（7-5），首尾间隔为 5（2+10-7），最大间隔为 5，则最小覆盖长度为 10-5+1=6。

2. 最优移位次数计算：

   • 若最大间隔是首尾间隔（环形的“断裂处”），则无需移位（次数为 0）。
   • 否则，最大间隔对应线性排列中的“空隙”，最优移位次数为空隙左侧起点或右侧终点到边界的最小距离。

代码解析

#include <stdio.h>
#include <algorithm>
#include <tuple>
typedef long long ll;
constexpr int N{100000};
int x[N + 5], y[N + 5];  // 存储行、列坐标

// 求解单行/列的最小覆盖长度和最少移位次数
std::tuple<int, int> solve(const int &l, const int &n, int *const &a) {
    std::sort(a + 1, a + n + 1);  // 排序坐标
    
    // 计算首尾间隔（环形）和相邻间隔，找到最大间隔
    int max_gap = a[1] + l - a[n];  // 首尾间隔（环形）
    for (int i = 2; i <= n; i++) {
        max_gap = std::max(max_gap, a[i] - a[i - 1]);  // 相邻间隔
    }
    
    int min_len = l - max_gap + 1;  // 最小覆盖长度
    
    // 若最大间隔是首尾间隔，无需移位
    if (a[1] + l - a[n] == max_gap) {
        return {min_len, 0};
    }
    
    // 否则，计算最小移位次数（取空隙两侧到边界的最小值）
    int min_shifts = l;  // 初始化为最大值
    for (int i = 2; i <= n; i++) {
        if (a[i] - a[i - 1] == max_gap) {
            // 左侧起点到左边界的距离 vs 右侧终点到右边界的距离（+1 是因为移位次数从1开始计数）
            min_shifts = std::min(min_shifts, a[i - 1]);
            min_shifts = std::min(min_shifts, l - a[i] + 1);
        }
    }
    
    return {min_len, min_shifts};
}

int main() {
    int h, w, n;
    scanf("%d%d%d", &h, &w, &n);  // 网格行、列数，画面数量
    
    // 读取画面坐标
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", x + i, y + i);
    }
    
    // 分别求解行和列的最小覆盖长度和最少移位次数
    auto [row_len, row_shifts] = solve(h, n, x);
    auto [col_len, col_shifts] = solve(w, n, y);
    
    // 总紧凑度 = 行长度 × 列长度；总移位次数 = 行移位 + 列移位
    printf("%lld %d\n", (ll)row_len * col_len, row_shifts + col_shifts);
    return 0;
}

关键步骤详解

1. 排序与间隔计算：

   • 对行（或列）坐标排序后，计算相邻元素的间隔和首尾环形间隔，最大间隔决定了“最宽松”的位置，最小覆盖长度由此推导。

2. 移位次数判断：

   • 若最大间隔是首尾间隔，说明画面已在环形排列中紧凑分布，无需移位。
   • 否则，最大间隔对应线性排列中的空隙，移位次数取空隙两侧到边界的最小距离（确保移动后空隙被“赶到”环形的边缘，使画面紧凑）。

3. 结果合并：

   • 总紧凑度是行和列最小覆盖长度的乘积。
   • 总移位次数是行和列各自最优移位次数的总和。

复杂度分析

• 时间复杂度：(O(k \log k))。排序操作占主导，适配 (k \leq 10^5) 的数据规模。
• 空间复杂度：(O(k))。存储行和列坐标，空间开销可控。

样例验证

以样例 1 为例：

• 输入为 1 行 10 列，3 个画面坐标为 (1,5)、(1,7)、(1,2)。
• 列坐标排序后为 [2,5,7]，首尾间隔为 (2 + 10 - 7 = 5)，相邻间隔为 3 和 2，最大间隔为 5。
• 最小覆盖长度为 (10 - 5 + 1 = 6)，无需移位，总紧凑度为 6×1=6，与样例一致。

样例 2 中，通过类似计算可得行和列的最小覆盖长度乘积为 4，总移位次数为 2，验证了算法的正确性。

该解法通过转化环形问题为线性间隔计算，高效求解最小紧凑度和最少移位次数，完美适配题目需求。