CSES 解决方案:数字螺旋

数字螺旋是一个无限大的网格,其左上角的方格中包含数字 1。我们的任务是找出第 Y 行第 X 列中的数字。下面是螺旋的前五层:

!NumberSpiral

示例:

> 输入: Y = 2, X = 3

> 输出: 8

> 解释: 第 2 行,第 3 列包含 8。

>

>

>

> 输入: Y = 4, X = 2

> 输出: 15

> 解释: 第 4 行,第 2 列包含 15。

解决思路: 要解决这个问题,我们可以遵循以下思路:

> 我们可以观察到,网格由许多正方形组成,且正方形边界上的数值要么按递增顺序排列,要么按递减顺序排列。答案位于边长为 Y 和 X 中最大值的正方形的边界上。因此,为了获取第 Y 行第 X 列的值,我们可以先计算内部正方形的面积,该正方形的边长比包含答案的边界所在正方形的边长小 1。然后,通过检查 Y 或 X 中较小值的奇偶性,将剩余的值加到内部正方形的面积上。可以观察到,对于网格中的偶数行,数字按递减顺序排列;而对于奇数行,数字沿逆时针方向按递增顺序排列。

!NumberSpiral2

分步算法:

  • 比较 Y 和 X:
  • 如果 Y > X
  • 计算内部正方形的面积,即 (Y-1)*(Y-1)。这代表那些不位于包含答案的正方形边界上的数字。
  • 现在要加上位于边界上的剩余数字,我们需要检查第 Y 行的奇偶性。如果第 Y 行是奇数,则直接将 X 加到内部正方形的面积上;否则,将 (2*Y – X) 加到面积上。
  • 否则(X >= Y):
  • 类似地,计算内部正方形的面积,即 (X-1)*(X-1)。这代表那些不位于包含答案的正方形边界上的数字。
  • 现在要加上位于边界上的剩余数字,我们需要检查第 X 列的奇偶性。如果第 X 列是偶数,则直接将 Y 加到内部正方形的面积上;否则,将 (2*X – Y) 加到面积上。这将得出最终答案。

下面是上述方法的实现:

C++


CODEBLOCK_1282595e

Java


“java

import java.util.*;

public class NumberSpiral {

// 计算数字螺旋中位置 处的值的函数

static void numberSpiral(long Y, long X) {

// 如果 Y 大于 X,意味着第 Y 行是外边界

if (Y > X) {

// 计算内部正方形的面积

long ans = (Y – 1) * (Y – 1);

long add;

// 检查 Y 的奇偶性以确定数字是递增还是递减顺序

if (Y % 2 != 0) {

// 如果第 Y 行是奇数,将 X 加到面积上

add = X;

} else {

// 如果第 Y 行是偶数,将 2*Y – X 加到面积上

add = 2 * Y – X;

}

// 打印最终结果

System.out.println(ans + add);

}

// 如果 X 大于或等于 Y,意味着第 X 列是外边界

else {

// 计算内部正方形的面积

long ans = (X – 1) * (X – 1);

long add;

// 检查 X 的奇偶性以确定数字是递增还是递减顺序

if (X % 2 == 0) {

声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。如需转载,请注明文章出处豆丁博客和来源网址。https://shluqu.cn/45195.html
点赞
0.00 平均评分 (0% 分数) - 0