题目:
题意:
一个国王和n个大臣,每个人左右手上都有一个数值。
现在将国王排在队首,将大臣进行排序。每个大臣的值是他前面所有人的左手值的积除以他自己右手的值。
问怎样的排序可以使得大臣的值中的最大值尽可能的小。
思路:
看题目感觉会是一个排序的问题,但是刚开始没想出来拿什么当关键字。
后来看了题解。感觉这种题目的关键是先考虑只有两个对象,分别计算这两个对象一前一后得到的答案,然后根据答案的不等式推出应该以什么作为关键字比较两个对象。
因此我们考虑一个大臣左右手的数值是a1,b1,另一个大臣走右手数值是a2,b2,国王的左右手数值是a0,b0
当1在前2在后时,可以得到$k1=a0/b1$和$k2=a0*a1/b2$,设此时答案是ans1
当2在前1在后时,可以得到$k3=a0/b2$和$k4=a0*a2/b1$,设此时答案是ans2
可以发现$k3<k2,k4>k1$
如果$ans1<ans2$恒成立也就是说我们要选择1在前2在后的情况,即$max(k1,k2)<max(k3,k4)$,那么$k4>k2$且$k4>k3$,此时$a2*b2>a1*b1$
这说明了左右手之积较小的应该放在前面。
推出了排序的规则,接下来就比较简单了。要注意的是这道题用到了大数。
1 import java.lang.reflect.Array; 2 import java.math.BigInteger; 3 import java.util.Arrays; 4 import java.util.BitSet; 5 import java.util.Comparator; 6 import java.util.Scanner; 7 8 public class Main { 9 private static class node{10 int lft;11 int rgt;12 }13 final static int maxn = 1005;14 static node[] peo;15 static Scanner scan = new Scanner(System.in);16 static int n;17 18 private static class cmp implements Comparator{19 @Override20 public int compare(node a, node b){21 if(a.lft * a.rgt < b.lft * b.rgt)return -1;22 else if(a.lft * a.rgt == b.lft * b.rgt)return 0;23 else return 1;24 }25 }26 public static void main(String[] args){27 n = scan.nextInt();28 peo = new node[n + 1];29 peo[0] = new node();30 peo[0].lft = scan.nextInt();31 peo[0].rgt = scan.nextInt();32 for(int i = 1; i <= n; i++){33 peo[i] = new node();34 peo[i].lft = scan.nextInt();35 peo[i].rgt = scan.nextInt();36 }37 Arrays.sort(peo, 1, n + 1, new cmp());38 39 BigInteger res = BigInteger.valueOf(peo[0].lft);40 BigInteger ans = BigInteger.ZERO;41 for(int i = 1; i <= n; i++){42 ans = ans.max(res.divide(BigInteger.valueOf(peo[i].rgt)));43 res = res.multiply(BigInteger.valueOf(peo[i].lft));44 }45 46 System.out.println(ans);47 }48 }