百度2019秋招笔试第1题完整推导及实现（鲤鱼算法）
1 牛牛给度度熊出了一道数学题，牛牛给定数字m,n,k，希望度度熊能找到一组非负整数a,b满足(n - a)(m - b) <= k且a+b尽量小。
示例：
输入：12 18 100
输出：7
分析：当a=7, b=0时，(n-a)(m-b)=90<=100=k, 此时a+b=7是最小的解
解：
（1）证明，当m,n,a,b均为非负整数且m>=n时，有 (m%20-%20b)%20%5Cge%20%5Bn%20-%20(a%20%2B%20b)%5Dm)
证：
结论：当n和m共需要减少a+b时，由n独自减少a+b，乘积下降的更多。
（2）解题思路1
基于上式，本题求解思路为：
将n, m中较小的数(如：n)不断减少，直到(n-c)m<k, 便可以保证c=a+b最小。
Python实现：
n, m, k = map(int, input().split()) if n > m: n, m = m, n c = 0 while (n - c) * m > k: c += 1 print(c)此时时间复杂度为O(n)。
（3）解题思路2
或者还可以进一步推导如下：
即a+b的最小值即为n-k/m, 此时时间复杂度为O(1)。
Python实现：
n, m, k = map(int, input().split()) if n > m: n, m = m, n print(n - k // m)
本文推导及实现由李同学与余同学自主完成，就暂记为鲤鱼算法吧。。哈哈。。
百度公司氛围 311人发布
投递百度等公司10个岗位 >
查看6道真题和解析