做网站服务器一年多少钱,做网站包含微信公众号吗,如何做网站网页免费,平顶山市湛河区建设局网站目录
题目部分
解读与分析
代码实现 题目部分
题目数字加减游戏难度难题目说明小明在玩一个数字加减游戏#xff0c;只使用加法或者减法#xff0c;将一个数字 s 变成数字 t 。 每个回合#xff0c;小明可以用当前的数字加上或减去一个数字。 现在有两种数字可以用来加减…目录
题目部分
解读与分析
代码实现 题目部分
题目数字加减游戏难度难题目说明小明在玩一个数字加减游戏只使用加法或者减法将一个数字 s 变成数字 t 。 每个回合小明可以用当前的数字加上或减去一个数字。 现在有两种数字可以用来加减分别为 a, b (a≠b)其中 b 没有使用次数限制。 请问小明最少可以用多少次 a才能将数字 s 变成数字 t 。 题目保证数字 s 一定能变成数字 t。输入描述输入的唯一一行包含四个正整数s,t,a,b(1≤s,t,a,b≤)并且a≠b。输出描述输出的唯一一行包含一个整数表示最少需要使用多少次 a 才能将数字 s 变成数字 t。补充说明无------------------------------------------------------示例示例1输入1 10 5 2输出1说明初始值 1 加一次 a 变成 6然后加两次 b 变成 10因此 a 的使用次数为 1。示例2输入11 33 4 10输出2说明11 减两次 a 变成 3然后加三次 b 变成 33因此 a 的使用次数为 2 次。 解读与分析
题目解读
由于 a 加一次后再减一次等于 0在这里需要计算最少次数所以我们不必做既加又减的操作。同时也假设 b 也只做一种操作也不存在既加又减的情况。
在这个前提下此题要求在 s 的基础上加减若干次 a再加减若干次 b最后得到 t。
本质上由 s 变成 t 与 由 t 变成 s相比加减 a 、b 的次数是一样的无非就是逆向操作加变减减变加。
更进一步思考s 变成 t与 ( s 1) 变成 ( t 1 ) 也是一样的其实就是发生 | s - t | 差值的变化。
分析与思路
由于 s、t 是固定值我们假设 n | s - t |。
此题可以转变为一个原始数据加或减a 若干次假设为 x加或减 b 若干次假设为 y产生的变化为 n 。 此题有 3 种情况 1. a * x - b * y n2. b * y - a * x n3. a * x b * y n其中x、y 均为正整数。 这 3 个等式可以做如下转换。 1. a * x - b * y n y 2. b * y - a * x n y 3. a * x b * y n y 其中 第 1 个 和 第 3 个 可以合并成 y 。
在 y 和 y 这两个等式中它们的分母都能被 b 整除这意味着这两个等式可以转换成 1. ( a * x ) % b n % b2. ( a * x ) % b ( b - n % b) % b这两个等式的右边都是常数。此题进一步简化找出最小的 x使其满足以上 2 个条件中的任意一个。
x 的取值范围是多少呢由于等式对 b 进行取模操作即意味着当 x 0 等同于 x b x 1 也等同于 x ( b 1)。直观地看 x 的取值范围为 0 ≤ x b。
更进一步假设 a、b 的最小公倍数是 L那么 a 加 次与 b 加 次是相等的因此 x 的取值范围可以进一步缩小到 0 ≤ x 。
那么此题就可以简化成把 x 从 0 到 代入到等式 1. ( a * x ) % b n % b2. ( a * x ) % b ( b - n % b) % b中当这两个等式中任意一个成立时x 的值即是最小的值。
题目中提到“题目保证数字 s 一定能变成数字 t”那我们在遍历时无需去计算 的值必定会在 之前求出 x 的值。
更进一步先求 a 与 b 的最大公约数设为 C1再求 n 与 b 的最大公约数C2接着求 C1 和 C2 的最大公约数设为 C那么等式就变成了 1. ( * x ) % % 2. ( * x ) % ( - % ) %
此时 与 的最小公倍数变为原来的 x 的范围进一步缩小。
但是写代码的时候完全不必关心这些。尽管 x 的取值范围进一步缩小x 的值不会发生改变从 0 开始遍历遍历的次数仍旧不会发生改变。
此题空间复杂度为 o(1)。由于输入数字最大不超过10的5次方运行时间很短。 代码实现
Java代码
import java.util.Scanner;/*** 数字加减游戏* * since 2023.09.08* version 0.1* author Frank**/
public class NumPlusMinusGame {public static void main(String[] args) {Scanner sc new Scanner(System.in);while (sc.hasNext()) {String input sc.nextLine();String[] numbers input.split( );processNumPlusMinusGame( numbers );}}private static void processNumPlusMinusGame( String numbers[] ){int s Integer.parseInt( numbers[0] );int t Integer.parseInt( numbers[1] );int a Integer.parseInt( numbers[2] );int b Integer.parseInt( numbers[3] );int n Math.abs( s - t );// 当modValue1 可能等于 modValue2如 modValue1 等于0 或 等于 b/2 的情况。int modValue1 n % b;int modValue2 ( b - n % b ) % b;int i 0;while( true ){int tmpModValue ( a * i ) % b;if( tmpModValue modValue1 || tmpModValue modValue2 ){System.out.println(i);return;}i ;}}
}
JavaScript代码
const rl require(readline).createInterface({ input: process.stdin });
var iter rl[Symbol.asyncIterator]();
const readline async () (await iter.next()).value;
void async function() {while (line await readline()) {var numberArr line.split( );processNumPlusMinusGame(numberArr);}}();function processNumPlusMinusGame(numberArr) {var s parseInt(numberArr[0]);var t parseInt(numberArr[1]);var a parseInt(numberArr[2]);var b parseInt(numberArr[3]);var n Math.abs(s - t);// 当modValue1 可能等于 modValue2如 modValue1 等于0 或 等于 b/2 的情况。var modValue1 n % b;var modValue2 (b - n % b) % b;var i 0;while (true) {var tmpModValue (a * i) % b;if (tmpModValue modValue1 || tmpModValue modValue2) {console.log(i);return;}i;}}
(完)
