题解 P1080 【国王游戏】
officeyutong
2017-10-30 22:33:48
看到诸位dalao还没有发java题解的，我这种蒟蒻先来发一个好了233
```java
//用java当然是为了用BigInteger 233
import java.math.BigInteger;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
//表示一个大臣
class Minister {
private int left;
private int right;
public Minister(int left, int right) {
this.left = left;
this.right = right;
}
public int getLeft() {
return left;
}
public void setLeft(int left) {
this.left = left;
}
public int getRight() {
return right;
}
public void setRight(int right) {
this.right = right;
}
}
public class Main {
//数据量不大 出于偷懒考虑直接用Scanner
Scanner scanner = new Scanner(System.in);
//题目所述的n
int n;
//存储各个大臣所对应的数据 0下标对应国王
Minister ministers[];
public void input() {
n = scanner.nextInt();
ministers = new Minister[n + 1 + 1];
for (int i = 0; i <= n; i++) {
ministers[i] = new Minister(scanner.nextInt(), scanner.nextInt());
}
}
public void process() {
//对大臣进行排序 为什么要这样下面的cpp大佬们已经说的很清楚了
//Arrays.sort(T[],a,b,Comparator) 对[a,b)区间进行排序
Arrays.sort(ministers, 1, n + 1, new Comparator<Minister>() {
@Override
public int compare(Minister o1, Minister o2) {
return (o1.getLeft() * o1.getRight() - o2.getLeft() * o2.getRight());
}
});
//计算到第i个大臣的时候 之前所有大臣左手上的数字的乘积(包括国王)
//题外话:为什么BigInteger没有BigInteger(int source)这个构造函数..
BigInteger prev = new BigInteger(String.valueOf(ministers[0].getLeft()));
//计算到第i个大臣时 前面所有大臣中所获的金钱最多的数目
BigInteger max = BigInteger.ZERO;
for (int i = 1; i <= n; i++) {
//特判 如果当前大臣所获得的金钱不足1 则改为1
if (prev.compareTo(new BigInteger(String.valueOf(ministers[i].getRight()))) < 0) {
if (new BigInteger("1").compareTo(max) > 0) {
max = new BigInteger("1");
}
} else {
BigInteger int1 = prev.divide(new BigInteger(String.valueOf(ministers[i].getRight())));
if (int1.compareTo(max) > 0) {
max = int1;
}
}
prev = prev.multiply(new BigInteger(String.valueOf(ministers[i].getLeft())));
}
System.out.println(max);
}
public static void main(String[] args) {
Main app = new Main();
app.input();
app.process();
}
}
```