PA 2019 Runda 1 Wina 题解

题目分析

这道题描述了一个经典的数塔问题，但有一个特殊的取数规则：要拿走一个数，必须满足它左上角和右上角的数已经被拿走（或者不存在）。我们需要拿走恰好 $k$ 个数，使得拿走的数中的最小值尽可能小。

解题思路

关键观察

1. 取数规则分析：

   • 要取位置 $(i,j)$ 的数，必须先取 $(i-1,j)$ 和 $(i-1,j+1)$ 的数
   • 这实际上形成了一个依赖关系

2. 问题转化：

   • 如果我们设定一个阈值 $x$，只考虑值 $\leq x$ 的数
   • 那么问题转化为：在只考虑值 $\leq x$ 的数的情况下，最多能取多少个数？

3. 贪心策略：

   • 对于每个位置 $(i,j)$，计算以它为顶点的三角形中最多能取多少个值 $\leq x$ 的数
   • 这个数量等于 $L \times R$，其中：
     • $L$ = 向左下延伸的最大长度
     • $R$ = 向右下延伸的最大长度

算法设计

代码采用了直接枚举 + 数学计算的方法：

1. 遍历所有位置：对于数塔中的每个位置 $(i,j)$
2. 计算可覆盖区域：
   • $L = j$（向左下能延伸的列数）
   • $R = i - j + 1$（向右下能延伸的列数）
3. 判断可行性：如果 $L \times R \leq k$，说明选择 $a[i][j]$ 作为最小值时，最多能取 $L \times R$ 个数
4. 更新答案：在所有满足条件的 $a[i][j]$ 中取最小值

代码详解

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 2111;

int n, k;
int a[N][N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    int ans = 3000;  // 初始化为一个较大的值

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= i; j++) {
            cin >> a[i][j];
            int L = j, R = i - j + 1;
            
            // 如果以(i,j)为顶点的三角形大小不超过k
            if (L * R <= k)
                ans = min(ans, a[i][j]);  // 更新最小值
        }

    cout << ans << "\n";
    return 0;
}

算法正确性证明

为什么是 $L \times R$？

对于位置 $(i,j)$：

• $L = j$：表示从 $(i,j)$ 向左下角延伸，最多能覆盖 $j$ 列
• $R = i - j + 1$：表示从 $(i,j)$ 向右下角延伸，最多能覆盖 $i-j+1$ 列
• $L \times R$：就是以 $(i,j)$ 为顶点的倒三角形区域的大小

为什么这样计算是正确的？

因为取数规则要求必须先取上方的数，所以如果我们选择 $a[i][j]$ 作为最小值，那么我们必须取整个以它为顶点的倒三角形区域内的所有数。这个区域的大小正好是 $L \times R$。

样例分析

对于题目样例：

5 7
1999
2019 2010
850 1500 1600
900 900 710 900
1000 800 600 800 1000

当考虑位置 $(4,3)$（值为 710）时：

• $i=4, j=3$
• $L = 3$（向左下延伸3列）
• $R = 4-3+1 = 2$（向右下延伸2列）
• $L \times R = 3 \times 2 = 6 \leq 7$

因此 710 是一个候选答案。

复杂度分析

• 时间复杂度：$O(n^2)$，需要遍历数塔中的所有位置
• 空间复杂度：$O(n^2)$，存储整个数塔

优化思路

虽然代码直接遍历所有位置已经足够高效，但还可以进一步优化：

1. 二分答案：对数值进行二分，检查是否存在一个阈值使得能取至少 $k$ 个数
2. 提前终止：当找到足够小的答案时可以提前结束

总结

这道题的关键在于发现取数规则的几何意义：每个位置 $(i,j)$ 对应一个大小为 $L \times R$ 的倒三角形区域。通过这个观察，我们将复杂的依赖关系转化为简单的区域大小计算，从而用 $O(n^2)$ 的复杂度解决了问题。

算法的巧妙之处在于：

1. 将取数依赖关系转化为几何区域
2. 通过直接计算区域大小判断可行性
3. 贪心地选择可能的最小值