时间戳

首页 > 解决方案 > 求解两个未知变量和两个函数

java - 求解两个未知变量和两个函数

问题描述

两个定义不同的函数。

 funcA:
    a = a - 2;
    b = b - 1;

 funcB: 
    a = a - 1;
    b = b - 2;

我们的目标是同时获得 和 时的操作 a = 0 次数 b = 0；

样本输入：a = 4, b = 2

  call funcA:
     a become 2, b become 1;
  again call funcA
     a become 0, b become 0;

执行的操作总数2 + 0 = 2返回2；

样本输入 2：a = 3, b = 3

  call funcA:
     a become 1, b become 2;
  call funcB
     a become 0, b become 0;

执行的操作总数1 + 1 = 2返回2；

标签： javaalgorithmdynamic-programming

解决方案

让我们从特殊情况开始：

  • 如果a < 0或者b < 0我们没有解决方案
  • if a = 0and b <> 0or a <> 0andb = 0我们没有解决方案
  • 如果a > 2 * b或者b > 2 * a我们没有解决方案

如果我们使用funcA x时间和funcB y时间并0从两者 a中获取，b我们可以写

a - 2 * x - y = 0
b - 2 * y - x = 0

让我们求解x和的线性方程组y：

2 * x + y = a
2 * y + x = b

解决方案是

x = (2 * a - b) / 3
y = (2 * b - a) / 3

因此，如果我们有一个整数解，x并且y我们应该执行funcA x次数，funcB y次数

代码（Java）：

public static int Solve(int a, int b) {
  // beware integer overflow! we use long in case a = 2_000_000_000 provided 
  long x = (2L * a - b) / 3;
  long y = (2L * b - a) / 3;

  return ((x >= 0 && y >= 0 && (2L * b - a) % 3 == 0 && (2L * a - b) % 3 == 0))
    ? (int)(x + y)
    : -1; // impossible
}

可以看出，我们有一个具有O(1)时间和空间复杂性的直接解决方案；不需要动态规划

推荐阅读