首页 > 试题广场 >

Tokitsukaze and Colorful Chess

[编程题]Tokitsukaze and Colorful Chess

热度指数：1556 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

Tokitsukaze 要在一个 $n \times n$ 的棋盘上摆放棋子。她有 $a$ 个红色的棋子和 $b$ 个蓝色的棋子，要求任意两个相同颜色的棋子上下左右四个方向不相邻，允许棋盘上留有不放棋子的空格子。

Tokitsukaze 想知道棋盘的边长 $n$ 至少多大，才能摆放下 $a$ 个红色的棋子和 $b$ 个蓝色的棋子。

输入描述:

第一行包含一个整数  () --- 测试数据的组数。

对于每组测试数据：

第一行包含两个整数 ,  (, ) --- 两种颜色的棋子数。

输出描述:

对于每组测试数据，输出一行，每行包含一个整数表示答案。

示例1

输入

2
4 5
0 6

输出

3
4

说明

第一组测试数据，我们只能这样摆：

第二组测试数据，我们可以这样摆：

算法知识视频讲解

Java

牛客203596504号

这道题很简单，首先观察题面的两个示例不难发现：

把棋盘填满，如果格子是偶数，两者各占一半，如果格子是奇数，两者相差一个。

所以：设a和b中较大的为max，那么n²>=max*2(偶数时)或者n²>=max*2-1(奇数时)
考虑到任何相邻平方数之差一定大于1，我们只需对max*2-1开平方后向上取整(棋盘必须是整数)
注意唯一的例外：当n是奇数，且max*2-1恰好等于n²，如果a=b，会有一枚棋子摆不下

代码两行：

int n = (int)Math.ceil(Math.sqrt(Math.max(a, b) * 2 - 1));
if (a + b > n * n) n++;

如果只想要AC，到此就可以结束了，但是……如果想要快呢？
开方是很耗时的操作，这里有10万条数据就要10万次开方，不划算。
考虑到数据范围是1e9，平方根最大44721，乘法比开方快很多！
我们完全可以打个平方表，然后用二分查找来求解。
具体代码就不贴了，如果不会打平方表，或者不会二分法的，就不用看这段了。

发表于 2026-03-11 01:53:56 回复(0)