优化网站排名,太原seo服务,网站触屏版,网站建设功能模块价格题目链接 [蓝桥杯 2015 省 B] 移动距离 题目描述 X X X 星球居民小区的楼房全是一样的#xff0c;并且按矩阵样式排列。其楼房的编号为 1 , 2 , 3 , . . . 1,2,3,... 1,2,3,...。
当排满一行时#xff0c;从下一行相邻的楼往反方向排号。
比如#xff1a;当小区排号宽度为…题目链接 [蓝桥杯 2015 省 B] 移动距离 题目描述 X X X 星球居民小区的楼房全是一样的并且按矩阵样式排列。其楼房的编号为 1 , 2 , 3 , . . . 1,2,3,... 1,2,3,...。
当排满一行时从下一行相邻的楼往反方向排号。
比如当小区排号宽度为 6 6 6 时开始情形如下 1 2 3 4 5 6 12 11 10 9 8 7 13 14 15 … 我们的问题是已知了两个楼号 m m m 和 n n n需要求出它们之间的最短移动距离。不能斜线方向移动
输入格式
输入三个整数 w , m , n w, m,n w,m,n空格分开都在 1 1 1 到 10000 10000 10000 范围内。 w w w 为排号宽度 m , n m,n m,n 为待计算的楼号。
输出格式
要求输出一个整数表示 m m m 与 n n n 两楼间最短移动距离。
输入输出样例
输入 6 8 2 输出 4 输入 4 7 20 输出 5 数据范围 1 ≤ w , m , n ≤ 1 0 4 1 \leq w,m,n \leq 10^4 1≤w,m,n≤104
解法找规律 模拟
我们先观察如下的矩阵 1 2 3 4 5 6 12 11 10 9 8 7 13 14 15 16 17 18 24 23 22 21 20 19 我们发现处于 奇数 行的编号 r r r其所在列的位置就是 c r % w c r \% w cr%w。举例 13 13 13 是在第 3 3 3 行其所在列的位置就是 c 13 % 6 1 c 13 \% 6 1 c13%61
我们发现处于 偶数 行的编号 r r r其所在列的位置就是 c w − ( r % w ) 1 c w - (r \% w) 1 cw−(r%w)1。举例 20 20 20 是在第 4 4 4 行其所在列的位置就是 c 6 − ( 20 % 6 ) 1 5 c 6 - (20 \% 6) 1 5 c6−(20%6)15
对于某一个编号 x x x 求其行数 r ⌈ x w ⌉ r \lceil \frac{x}{w} \rceil r⌈wx⌉即 r x w − 1 w r \frac{x w - 1}{w} rwxw−1。举例对于编号 13 13 13他所在的行数为 13 6 − 1 6 3 \frac{13 6 - 1}{6} 3 6136−13。
对于 m m m 和 n n n 我们分别求出他们行的位置 r 1 , r 2 r_1, r_2 r1,r2 和 列的位置 c 1 , c 2 c_1,c_2 c1,c2。
最好求出距离即 a n s ∣ r 1 − r 2 ∣ ∣ c 1 − c 2 ∣ ans |r_1 - r_2| |c_1 - c_2| ans∣r1−r2∣∣c1−c2∣ 。
时间复杂度 O ( 1 ) O(1) O(1)
C代码
#includeiostreamusing namespace std;int main() {int w, m, n;cinwmn;int r1 (m w - 1) / w, r2 (n w - 1) / w;int c1 0, c2 0;if(r1 1){c1 m % w;}else{c1 w - (m % w) 1;}if(r2 1){c2 n % w;}else{c2 w - (n % w) 1;}int ans abs(r1 - r2) abs(c1 - c2);coutans\n;return 0;
}Java代码
import java.util.*;
import java.io.*;public class Main {static BufferedReader in new BufferedReader(new InputStreamReader(System.in));public static void main(String[] args) throws Exception {String[] str in.readLine().split( );int w Integer.parseInt(str[0]);int m Integer.parseInt(str[1]);int n Integer.parseInt(str[2]);int r1 (m w - 1) / w;int r2 (n w - 1) / w;int c1 0;int c2 0;if((r1 1) 1) {c1 m % w;}else {c1 w - (m % w) 1;}if((r2 1) 1) {c2 n % w;}else {c2 w - (n % w) 1;}int ans Math.abs(r1 - r2) Math.abs(c1 - c2);System.out.println(ans);}
}
