解题思路

1. 对角线长度的分布

棋盘上共有 $2n-1$ 条不同的对角线（$i+j$ 的取值范围为 $2,3,\dots,2n$）。
对于第 $s$ 条对角线（即 $i+j=s$），它的格子数量（长度）为：

• 当 $2 \le s \le n+1$ 时，长度为 $s-1$（递增）；
• 当 $n+2 \le s \le 2n$ 时，长度为 $2n+1-s$（递减）。

因此长度序列为：

其中长度为 $n$ 的对角线只有 一条（即 $i+j=n+1$ 的主对角线）；
其余长度 $1,2,\dots,n-1$ 均出现 两次（对称的两条）。

2. 贪心策略

为了尽量减少被占用的对角线数量，我们应尽可能将棋子 集中 在尽可能少的对角线上。
因此优先选取 容量最大 的对角线来放置棋子。

贪心过程：

1. 将所有对角线按长度从大到小排序（显然先取长度为 $n$ 的那一条，然后取两条长度为 $n-1$ 的，再取两条长度为 $n-2$ 的，……）。
2. 依次填充每条对角线，直到所有 $k$ 个棋子都放完。
3. 此时所使用的对角线数量即为最少被占用的对角线数。

3. 正确性证明

• 若存在一个最优解，其中某条较短的对角线被填满了，而某条更长的对角线尚未被完全利用，那么我们可以将棋子从短对角线移动到长对角线上（因为长对角线的剩余空位更多），这样不会增加占用对角线的数量，甚至可能减少。
• 因此存在一个最优解，它按照对角线长度从大到小的顺序依次填满。
• 贪心算法正好模拟了这个过程，所以得到最优解。

4. 算法实现

直接模拟即可：

1. 初始化一个数组 len，包含所有对角线的长度：先放一个 $n$，然后从 $i=n-1$ 向下到 $1$，每个 $i$ 放两次。
2. 将 len 从大到小排序（其实已经有序）。
3. 遍历 len，用当前长度 l 尝试放棋子：
   • 若 $k \le l$，则放完 $k$ 个棋子，答案加 $1$，结束。
   • 否则 $k \leftarrow k - l$，答案加 $1$，继续下一条对角线。

复杂度 $O(n)$ 每条对角线处理一次。

5. 边界情况

• $k = 0$：不需要任何棋子，占用对角线数为 $0$。
• $k = n^2$：必须放满整个棋盘，所有对角线都被占用（共 $2n-1$ 条），答案即为 $2n-1$。

示例讲解

以题目样例为例：

例2： $n=2, k=2$
对角线长度：$[2,1,1]$（一条长度 $2$，两条长度 $1$）。
先填长度 $2$ 的对角线，可放 $2$ 个棋子 → $k$ 用完，占用 $1$ 条对角线。输出 $1$。

例3： $n=2, k=3$
先填长度 $2$（放 $2$ 个，$k$ 剩 $1$），再填一条长度 $1$（放 $1$ 个），占用 $2$ 条对角线。输出 $2$。

例4： $n=2, k=4$
填满长度 $2$（$2$ 个），再填两条长度 $1$（各 $1$ 个），占用 $3$ 条对角线。输出 $3$。

例7： $n=3, k=9$
对角线长度：$[3,2,2,1,1]$，总容量 $3+2+2+1+1=9$，需要全部填满，占用 $5$ 条对角线。输出 $5$。

参考代码

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

int solve(int n, int k) {
    if (k == 0) return 0;
    
    // 按长度从大到小列出所有对角线
    vector<int> diag;
    // 先放最长的（长度 n）
    diag.push_back(n);
    // 然后放长度 n-1, n-2, ..., 1，每个长度出现两次
    for (int i = n-1; i >= 1; --i) {
        diag.push_back(i);
        diag.push_back(i);
    }
    
    int ans = 0;
    for (int len : diag) {
        if (k <= len) {
            ans++;       // 当前对角线能放下剩余所有棋子
            break;
        }
        k -= len;        // 填满这条对角线
        ans++;
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;
        cout << solve(n, k) << '\n';
    }
    return 0;
}

时间复杂度

每个测试用例 $O(n)$，总复杂度 $O(t \cdot n) \le 5 \times 10^4$，轻松通过.