给定两个数字 n
和 k
, 查找 x
, 1 <= x <= k
使余数最大化 n % x
.
例如,n = 20 和 k = 10,解是 x = 7,因为余数 20 % 7 = 6 是最大值。
我对此的解决方案是:
int n, k;
cin >> n >> k;
int max = 0;
for(int i = 1; i <= k; ++i)
{
int xx = n - (n / i) * i; // or int xx = n % i;
if(max < xx)
max = xx;
}
cout << max << endl;
但我的解决方案是
O(k)
.有没有更有效的解决方案?
最佳答案
不是渐近地更快,而是更快,只需向后退并在您知道自己不能做得更好时停下来。
假设 k
小于 n
(否则只输出 k
)。
int max = 0;
for(int i = k; i > 0 ; --i)
{
int xx = n - (n / i) * i; // or int xx = n % i;
if(max < xx)
max = xx;
if (i < max)
break; // all remaining values will be smaller than max, so break out!
}
cout << max << endl;
(这可以通过做 for 循环来进一步改进,只要
i > max
,从而消除一个条件语句,但我这样写是为了让它更明显)另外,请查看 Garey 和 Johnson 的 Computers and Intractability 一书,以确保这不是 NP-Complete(我确定我记得那本书中的一些问题看起来很像这样)。在投入太多精力试图提出更好的解决方案之前,我会这样做。
关于c++ - 如何找到除数以最大化余数?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/68405540/