在N班中分配B奶酪蛋糕，以儘量減少每個蛋糕的學生最大數量

Question

村裏有一所學校。它有N個類。有一天，有人向學校捐贈了B藍漿果芝士蛋糕。現在你需要把這些蛋糕分成這樣的：

每個班級至少得到1個蛋糕。 每個班級將分享學生之間的蛋糕。 您的目標是最大限度地減少任何班級每個蛋糕的最大學生人數。

輸入

包含兩個空間隔開的整數N和B上分別表示的類和總數藍色漿果芝士蛋糕的，數量。 接下來的N行包含每個班級的學生人數。

輸出 對於每個測試用例，輸出將共享蛋糕的學生的最大數量。 約束 = N < = 5 * 10^5

Ñ< = B < = 2 * 10^6 1 < =學生在第i級的數目< = 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; 
} 
}