欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-06-09 20:14:35
贪心排序与Java类排序的使用链接难度题意数据范围思路Java 怎么把多个类放在一个class里面?Java 搞动态数组?怎么用?Java怎么使用类排序?怎么自定义比较顺序?核心代码链接国王游戏 | 洛谷 P1080难度普及+/提高\color{green}普及+/提高普及+/提高需要注意许多点的绿题。学了一些Java的类排序技巧。题意有一位国王和 nnn 位大臣。每个人有两个数字 a、ba、ba、b国王排第一,后面的大臣你自己排序。排好后,每位大臣的奖赏为他前面所有人的 aaa的乘积除...

链接

国王游戏 | 洛谷 P1080

难度

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

题意

有一位国王和 n n n 位大臣。每个人有两个数字 a 、 b a、b ab
国王排第一,后面的大臣你自己排序。
排好后,每位大臣的奖赏为他前面所有人的 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=bij<iaj
你需要使得最大奖赏的人的奖赏值最小,即求:
min ⁡ { g e t i } \min\{get_i\} min{geti}

数据范围

1 ≤ n ≤ 1000 1\le n\le 1000 1n1000
0 < a , b < 10000 0<a,b<10000 0<a,b<10000

思路

  1. 考虑两个人时候的排序
    【贪心排序与Java类排序的使用】国王游戏
  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 × b a\times b a×b的值。
  • 使用比较器排序
    Collections.sort(nodes,compareAB);按照 a × b a\times b a×b升序排序
    Collections.sort(nodes,compareAB.reversed();按照 a × b a\times b a×b降序排序
    Collections.sort(nodes,compareA.thenComparing(compareB);按照 a a a升序排序,如果其相同则按照 b b 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