Uva13177 - Orchestral scores

題目大意

樂團表演時需要樂譜，但錢不夠所以需要限制譜的數量，其中同個樂器可以看同張譜，但是太多人一起看又太不美觀了，於是我們要找出在譜數量的限制下，最少的最大看同個譜的人數(每個樂器中最大的)

重點觀念

• 二分搜

分析

• 原本以為用 Priority Queue ，每次把最大抓來除以二丟回就好，但似乎沒這麼簡單
• 後來參考大大發現去用各樂器同時看譜人數降低到指定數目所需要的譜數量來做判斷，就可以找出答案

程式題目碼

#include <iostream>
#include <queue>
using namespace std;

void print_pq(priority_queue<int, vector<int>, less<int> > pq) {
    while (pq.size() > 0) {
        cout << pq.top() << " ";
        pq.pop();
    }
    cout << endl;
}

int main() {
    int p, n;
    while (scanf("%d %d", &p, &n) == 2) {
        int a[n];
        int min_number = 1, max_number = 0;
        for (int i = 0; i < n; i++) {
            int num;
            scanf("%d", &a[i]);
            max_number = max(max_number, a[i]);
        }

        int ans = 1;
        while (min_number <= max_number) {
            int m = (min_number + max_number) / 2;
            int score = 0;
            for (int i = 0; i < n; i++) {
                score += ((a[i] + m - 1) / m);
            }

            if (score <= p) {
                max_number = m - 1, ans = m;
            } else {
                min_number = m + 1;
            }
        }

        cout << ans << endl;
    }

    return 0;
}