题目描述

利用二分的思想去分V值，以此去找不同情况下的最大值和最小值。
left=1,因为V值不可能为0

样例

import java.util.*;

public class Main {

    static class Pair {
        int x, y;

        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    static final int N = 10010;
    static int n;
    static Pair[] a = new Pair[N];

    static boolean check1(int mid) {

        for (int i = 1; i <= n; i++)
            //如果此时大于了给定的产量 说明最小值偏小了 返回false
            if (a[i].x / mid > a[i].y) return false;
        //此时就是最小值偏大了 返回true
        return true;
    }

    static boolean check2(int mid) {

        for (int i = 1; i <= n; i++)
            //如果此时小于了给定的产量 说明最大值偏大了 返回false
            if (a[i].x / mid < a[i].y) return false;
        //此时就是最大值偏小了 返回true
        return true;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        for (int i = 1; i <= n; i++)
            a[i] = new Pair(scanner.nextInt(), scanner.nextInt());

        int left = 1, right = (int) 1e9;
        while (left < right) {
            int mid = left + right >> 1;
            if (check1(mid)) right = mid;
            else left = mid + 1;
        }

        System.out.print(right + " ");

        right = (int) 1e9;
        while (left < right) {
            int mid = left + right + 1 >> 1;
            if (check2(mid)) left = mid;
            else right = mid - 1;
        }

        System.out.println(right);
    }
}