最小值

[编程题]最小值

热度指数：1395 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

牛牛给度度熊出了一个数学题，牛牛给定数字 $\mathit n,m,k$ ，希望度度熊能找到一组非负整数 $\mathit a,b$ 满足 $(n-a)(m-b) \leq k$ 且 $\mathit a+b$ 尽量小。

度度熊把这个问题交给了你，希望你能帮他解决。

输入描述:

一行三个数字

输出描述:

输出最小的。

示例1

输入

12 18 100

输出

说明

当时候, ，此时是最小的解。

算法知识视频讲解

Java

热衷技术的小羽

用java求解，非数学方法

思路：

1、 $(n - a)(m - b)<=k$ 当 a 逐渐增大，b值假设固定，则 $(n - a)(m - b)$ 单调递减，则不等式必然可以能够成立。

2、利用这点则 $b\geq m-k/(n-a)$ ，则当 $b= m-k/(n-a)$ （因为长整型）在该工况下a+b取到最小值

3、最后 min（min，a+b）

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        long n = in.nextLong();
        long m = in.nextLong();
        long k = in.nextLong();

        long a = 0;
        long b = 0;
        long min = Integer.MAX_VALUE;

        for (; a < n; a++) {
            b = m - k / (n - a);
            if (b >= 0) {
                min = a + b < min ? a + b : min;
            } else {
                b = 0;
                min = a + b < min ? a + b : min;
                break;
            }
        }
        min = a < min ? a : min;

        System.out.print(min);
    }
}