技巧:
单维度套路贪心
思路:
------A,B------ (交换 A和B的顺序不影响前面人和后面人的结果)
实现: (当时应为整数计算溢出被坑了不少时间... 一直AC不掉)
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.StreamTokenizer; import java.math.BigInteger; import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; import java.util.List; public class Main { public static void main(String[] args) throws IOException { //接收入参 Input in = new Input(); long n = in.nextInt(); BigInteger t = BigInteger.valueOf(in.nextInt()); in.nextInt(); BigInteger ans = BigInteger.ZERO; List<Hand> list = new ArrayList<>(); for (int i = 0; i < n; i++) { list.add(new Hand(BigInteger.valueOf(in.nextInt()), BigInteger.valueOf(in.nextInt()))); } // 排序 (贪心) Collections.sort(list, (o1, o2) -> o1.left.multiply(o1.right).compareTo(o2.left.multiply(o2.right))); // 找出结果 for (int i = 0; i < n; i++) { BigInteger temp = t.divide(list.get(i).right); ans = ans.compareTo(temp) >= 0 ? ans : temp; t = t.multiply(list.get(i).left); } System.out.print(ans.toString()); } static class Input { StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); public long nextInt() throws IOException { in.nextToken(); return (long) in.nval; } } static class Hand { private BigInteger left; private BigInteger right; public Hand(BigInteger left, BigInteger right) { this.left = left; this.right = right; } } }