ケーキ1杯あたりの生徒数を最小限に抑えるために、NクラスにBチーズケーキを割り振る。

Question

村に学校がある。それはN個のクラスを持っています。ある素晴らしい日、誰かがBブルーベリーチーズケーキを学校に寄付しました。今度は、これらのケーキを次のように分割する必要があります。

各クラスに少なくとも1ケーキがあります。 各クラスは学生の間でケーキを共有します。 あなたの目的は、どのクラスでもケーキ当たりの生徒の最大数を最小限に抑えることです。

入力

それぞれクラスおよびブルーベリーチーズケーキの総数の数を示す2スペースで区切られた整数NおよびBを含有します。 次のN行には、各クラスの生徒数が含まれています。

出力 ケーキを共有する生徒の最大数を出力します。 制約 = N < = 5 * 10^5

N < = 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に同意します。このソリューションはかなりシンプルで、1つのケーキと各クラスで最大ヒープを初期化します。 1つずつケーキを配布し始めます。ここでは、ソリューションの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; 
} 
}