题解：P11697 [ROIR 2025] 二维蚱蜢 (Day 1)

数据太大，深搜做不了，只能用数学贪心的思想。。

声明：1,1到n,m和1,1到m,n最短路步数相同，所以 if(n>m)swap(n,m);

计算是从0,0开算的，而题目是从1,1开走的,所以要 n--; m--;

上思路：

首先，我把路径分成两段

上图： n=4 m=7


1
	1
		1	2	2	2

. . . . . . . . . . . . . . . . . . . . . . . . . . . .

1为第一段路。 第一段路走的是一个长为n的斜线

2为第二段路。 第二段路走的是一条长为(m-n)的直线

分别求出走两段路的步数：

第一段路 (n-1)*1.0/k+1

第二段路 (m-n-1)*1.0/k+1

最后把两段步数相加，即为最终答案。

直接上代码：

CPP

#include<bits/stdc++.h>
using namespace std;
int n,m,k;
int main()
{
	cin>>n>>m>>k;
	n--;m--;
	if(n>m)swap(n,m);
	int ans=0;
	if(m-n>=1)ans+=(m-n-1)*1.0/k+1;
	ans+=(n-1)*1.0/k+1;
	cout<<ans;
}

题解：P11697 [ROIR 2025] 二维蚱蜢 (Day 1)

文章操作

相关推荐

评论

题解：P11697 [ROIR 2025] 二维蚱蜢 (Day 1)