**

题目描述

**
给 Vitaly503 一个方格棋盘，棋盘的一边是 n 和 k 个筹码。他意识到所有这些 k 芯片都需要放置在棋盘的单元格上（一个单元格上不能放置超过一个芯片）。

让我们把第 i 行和第 j 列中的单元格表示为 (i ,j) 。对角线是指 i + j 值相同的单元格集合。例如， (3, 1) 、 （2, 2) 和 (1, 3) 位于同一条对角线上，而 (1, 2) 和 (2, 3) 不在同一条对角线上。如果一条对角线上至少有一个单元格，那么这条对角线就被称为 "占用 "对角线。

请判断在所有放置 k 的筹码中，被占对角线的最少数目是多少。

**

输入

**

每个测试由多组输入数据组成。第一行包含一个整数 t ( 1 \le t \le 500 ) - 输入数据集的数量。然后是各组输入数据的说明。

每组输入数据的唯一一行包含两个整数 n , k ( 1 \le n \le 100, 0 \le k \le n^2 ) - 分别是棋盘的边数和可用筹码数。
**

输出

**

对于每组输入数据，输出一个整数--在放置所有 k 个筹码后，他能得到的至少有一个筹码的对角线的最小占位数。

我们这道题目可以通过画图来解决
接下来是画图的过程
**

画图分析

**
CF1995A.Diagonals题解（CN）.jpg

通过这个图片，我们可以得知，最长的一条对角线的值为n,只有一条
而次短的对角线就有2条，长度为n-1
依此类推，知道长度为1
求解最短的对角线使用数量
那么我们就可以使用贪心思想
先用最大的，最大的用完了，再用次小的，再用次次小的，依此类推

代码展示

#include <bits/stdc++.h>
using namespace std;
int main(){
    long long t,n,k;
    cin>>t;
    while(t--){
        cin>>n>>k;
        long long count=0;
        if(k<=n){
            if(k>0) {
                cout<<'1'<<endl;
                continue;
            }
            else{
                cout<<'0'<<endl;
                continue;
            }
        }
        k=k-n;
        n=n-1;
        while(k>0){
            if(n==0){
                break;
            }
            k=k-n;
            count++;
            if(count%2==0)n=n-1;
        }
        cout<<count+1<<endl;
    }
    return 0;
}
最后修改：2025 年 03 月 22 日
© 禁止转载
如果觉得我的文章对你有用，请随意赞赏