「题解」Luogu 1080「国王游戏」

分析

这题以$l_i\times r_i$为关键字排序就行了,证明可用邻项交换。

要用高精,Java水过

代码

//package xyz.cinema000.luogu;

import java.io.BufferedInputStream;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

class Person implements Comparable<Object>{
    BigInteger l,r;
    Person(){}
    Person(BigInteger l,BigInteger r){
        this.l = l;
        this.r = r;
    }

    @Override
    public int compareTo(Object o) {
        BigInteger delta1 = BigInteger.ONE,delta2 = BigInteger.ONE;
        Person p = (Person)o;
        delta1 = this.l.multiply(r);
        delta2 = p.l.multiply(p.r);
        return delta1.compareTo(delta2);
    }

}

public class Main{
    public static void main(String[] args) {
        Scanner in = new Scanner(new BufferedInputStream(System.in));
        int n = in.nextInt();
        BigInteger delta1,delta2,max = BigInteger.ZERO;
        ArrayList<Person> P = new ArrayList<Person>();
        Person king = new Person();
        king.l = in.nextBigInteger();
        king.r = in.nextBigInteger();
        for(int i = 0;i < n;i++) {
            delta1 = in.nextBigInteger();
            delta2 = in.nextBigInteger();
            P.add(new Person(delta1,delta2));
        }
        Collections.sort(P);

        delta1 = BigInteger.ONE;
        delta1 = delta1.multiply(king.l);
        for(int i = 0;i < n - 1;i++) {
            delta1 = delta1.multiply(P.get(i).l);
        }
        max = delta1.divide(P.get(n - 1).r);
        if(max.compareTo(BigInteger.ZERO) <= 0) max = BigInteger.ONE;
        System.out.println(max);

    }
}