二维表第k大数

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		int k = sc.nextInt();

		int start = 1;
		int end = n * m;
		while (start < end) {
			// 中位数, 这里不写成 mid = (start + end) / 2, 是为了防止整型溢出
			int mid = start + (end - start) / 2;
			// 记录数组中比mid大的数值个数
			int cnt = 0;
			// 记录数组中刚好大于mid的整数值
			// 例如mid = 50时, 若数组中大于50的数中最小值为51, 则res = 51. 
			int res = n * m;
			// 大于mid的数, 其x必大于mid/m, 其y必大于mid/n
			for (int i = mid / m + 1; i <= n; i++)
				for (int j = mid / n + 1; j <= m ; j++)
					// 找到第一个满足条件的数后, 直接将该列后续所有数字加进来, 减少复杂度, 非常重要!!!!
					if (i * j > mid) {
						cnt += (m - j + 1);
						if (res > i * j)
							res = i * j;
						// 这里的break只能跳出最内层的for循环
						break;
					}

			if (cnt > k)
				start = mid + 1;
			else if (cnt == k) {
				// 当cnt == k时, 直接取res即可
				start = res;
				break;
			} else if (cnt < k)
				// 这里不能令end = mid -1,否则有可能将最优解滤除
				// 假设大于50的数有19个, 等于50的数有3个, 此时cnt = 19, 若k = 20,
				// 最优解应为50, 故不能令end = mid -1
				end = mid;
		}
		System.out.println(start);
	}
}

import java.util.Scanner;

public class Main{
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int M = in.nextInt();
        int K = in.nextInt();
        int l = 0;
        int h = M * N;
        //反向序号
        K = M * N - K + 1;
        while (l <= h) {
            int mid = l + (h - l) / 2;
            // 假定以mid作为最大数的所在行curRow; 由矩阵的特点可知：
            // curRow的上一行所有的数都将小于mid，缩小查找范围
            int curRow = mid / M;
            // 同理，获取所在列curCol；
            int curCol = mid / N;
            int cnt = curRow * M + curCol * (N - curRow);
            // 剩下右下角一个小矩形
            for (int i = curRow + 1; i <= N; i++) {
                for (int j = curCol + 1; j <= M && (i * j <= mid); j++) {
                    cnt++;
                }
            }
            if (cnt >= K) {
                h = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        System.out.println(l);
    }
}