【贪心排序与Java类排序的使用】国王游戏

贪心排序与Java类排序的使用

• • 链接
  • 难度
  • 题意
  • 数据范围
  • 思路
  • • Java 怎么把多个类放在一个class里面？
    • Java 搞动态数组？怎么用？
    • Java怎么使用类排序？怎么自定义比较顺序？
  • 核心代码

链接

国王游戏 | 洛谷 P1080

难度

普

及

+

/

提

高

\color{green}普及+/提高

普及+/提高
需要注意许多点的绿题。
学了一些Java的类排序技巧。

题意

有一位国王和

n

n

n 位大臣。每个人有两个数字

a

、

b

a、b

a、b
国王排第一，后面的大臣你自己排序。
排好后，每位大臣的奖赏为他前面所有人的

a

a

a的乘积除以他自己的

b

b

b 向下取整。
即：

g

e

t

i

=

⌊

∏

j

<

i

a

j

b

i

⌋

get_i=\Bigg\lfloor\frac{\underset{j<i}{\prod}a_j}{b_i}\Bigg\rfloor

geti​=⌊bi​j<i∏​aj​​⌋
你需要使得最大奖赏的人的奖赏值最小，即求：

min

⁡

{

g

e

t

i

}

\min\{get_i\}

min{geti​}

数据范围

1

≤

n

≤

1000

1\le n\le 1000

1≤n≤1000

0

<

a

,

b

<

10000

0<a,b<10000

0<a,b<10000

思路

1. 考虑两个人时候的排序
2. 两个人也可以推到多个人。方法相同
3. 这个时候，因为

   ∏

   a

   j

   \prod a_j

   ∏aj​ 特别大，我们需要使用高精度。这里选择方便的Java。

Java 怎么把多个类放在一个class里面？

• 这个蠢问题困扰了我几个月，现在终于搞明白了……

public class Main {
	static class node {
		/// balabala
	}
	public static void main(String[] args) {
		/// balabala
	}
}

• 为什么在自定义的node类前要写 static呢？（因为不写，new一个会报错）

Java 搞动态数组？怎么用？

• C++有方便的 vector、List，Java也有List，它是一个接口，里面有 ArrayList, Linked List, vector
• 怎么简单地使用？（内容太多了，就搞点这题用到的吧）
  注意要大写
• 声明
  List<Integer> L1= new ArrayList<Integer>();整数型的List
  LinkedList<Double> L2 = new LinkedList<Double>();Double型的LinkedList
  List<node> nodes = new ArrayList<node>();类node类型的List
• 插入（自己可以写一个构造函数）
  nodes.add(new node(something));

Java怎么使用类排序？怎么自定义比较顺序？

• 定义比较器
  Comparator<node> compareAB =Comparator.comparing(node::getAB);
  其中的 getAB 是类中的方法，获得$a\times b$
• 使用比较器排序
  Collections.sort(nodes,compareAB);按照$a\times b$

基本就是这么多了，这题就可以写了！

注意下国王的位置是不能变的，需要排序的是所有大臣的位置。

核心代码

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
import java.math.*;

public class Main {
	static class node {
		public BigInteger a;
		public BigInteger b;
		node(BigInteger a,BigInteger b){
			this.a = a;
			this.b = b;
		}
		BigInteger getAB() {
			BigInteger c = this.a.multiply(this.b);
			return c;
		}
		BigInteger getA() {
			return this.a;
		}
		BigInteger getB() {
			return this.b;
		}
	}
	public static void main(String[] args) {
		Scanner read = new Scanner(System.in);
		Comparator<node> compareAB =
				Comparator.comparing(node::getAB);
		List<node> nodes = new ArrayList<node>();
		int n = read.nextInt();
		BigInteger ka = read.nextBigInteger();
		BigInteger kb = read.nextBigInteger();
		for(int i = 0;i < n;++i) {
			BigInteger ta = read.nextBigInteger();
			BigInteger tb = read.nextBigInteger();
			nodes.add(new node(ta, tb));
		}
		Collections.sort(nodes,compareAB);
		BigInteger sum = ka;
		BigInteger mx = BigInteger.valueOf(0);
		for(node it : nodes) {
			mx = mx.max(sum.divide(it.getB()));
			sum = sum.multiply(it.getA());
		}
		System.out.println(mx);
		read.close();
	}	
}

本文地址：https://blog.csdn.net/weixin_45775438/article/details/109946950