Разделение сырных пирогов B среди N классов, чтобы свести к минимуму максимальное количество учащихся на торт

Question

В деревне есть школа. Он имеет N классов. В один прекрасный день, кто-то пожертвовал B синие ягодные пирожные в школу. Теперь вам нужно разделить эти торты так, чтобы:

Каждый класс получает не менее 1 тортов. Каждый класс будет делиться пирожными среди учащихся. Ваша цель - свести к минимуму максимальное количество учащихся на каждый торт в любом классе.

вход

содержит два целых числа пространства Н и В, обозначающее количество классов и общего количества голубых сыра ягодные торты, соответственно. Следующие N строк содержат количество учеников в каждом классе.

Выход Для каждого тестового примера выведите максимальное количество студентов, которые будут делиться пирожным. Ограничения = N < = 5 * 10^5

Н < = В < = 2 * 10^6 1 < = число студентов в классе-го < = 5 * 10^6

Образец Входной сигнал - 1 1 2 35 Выход для образца - 1 18 Вход для образца - 2 2 7 20 50 Выход для образца - 2 10

Answer 1

Я согласен с smartsn123. Решение довольно простое, инициализируйте максимальную кучу с каждым классом одним пирогом и затем начните раздавать торты один за другим. Здесь следует реализация Java-решения.

import java.util.*; 
class Node{ 
    private int nStu ; 
    private int nCake; 
    public Node(int nStu , int nCake){ 
     this.nStu = nStu; 
     this.nCake = nCake; 
    } 
    public int getnStu(){ 
     return nStu; 
    } 
    public int getnCake(){ 
     return nCake; 
    } 
    public void addCake(){ 
     nCake++; 
    } 
} 
class CheeseCake{ 

public static void main(String[] args){ 

    Scanner sc = new Scanner(System.in); 
    int N = sc.nextInt(); 
    int B = sc.nextInt(); 
    int[] arr = new int[N]; 
    int ext = B - N ; 
    MyComparator mc = new MyComparator(); 
    PriorityQueue<Node> queue = new PriorityQueue<>(mc); 
    for(int i = 0 ; i < N ; i++){ 
     //arr[i] = sc.nextInt(); 
     int temp = sc.nextInt(); 
     Node newNode = new Node(temp , 1); 
     queue.add(newNode); 
    } 
    while(ext != 0){ 
     Node new1 = queue.poll(); 
     new1.addCake(); 
     queue.add(new1); 
     ext--; 
    } 
    Node newNode1 = queue.poll(); 
    int fStu = newNode1.getnStu(); 
    int fCake = newNode1.getnCake(); 
    System.out.println((fStu+1)/2); 

} 
} 
class MyComparator implements Comparator<Node>{ 
@Override 
public int compare(Node n1 , Node n2){ 
    /*arranging based on the students per cakes*/ 
    double avg1 = n1.getnStu()/n1.getnCake(); 
    double avg2 = n2.getnStu()/n2.getnCake(); 
    if(avg1 > avg2){ 
     return -1; 
    } 
    if(avg1 < avg2){ 
     return 1; 
    } 
    return 0; 
} 
}