UVa13177 - Orchestral scores(Binary Search 二分搜尋)

題目大意

一個古典樂團要進行演奏，通常古典樂團是許多樂器、許多人一起搭配而成，例如：演奏小提琴有 8 個人、中提琴有 4 個、大提琴有 2 個，由於每次演奏的曲譜都不一樣，要帶著走很不方便。
如果每個樂手都有一份譜，古典樂一份樂譜至少要 100 張紙以上，這很不環保、浪費成本，因此我們希望可以讓同個樂器的人可以共同看一份樂譜，但是如果讓一群人只看一張樂譜會讓聽眾視覺觀感不好，因此指揮會讓同個樂器的人拿到很多份樂譜，來降低讓觀眾視覺觀感不好。

因此我們希望給你 p 張譜，n 種樂器、其中每種樂器都有很多人，請告訴我們在以讓最少人一起看樂譜的前提下，最多會有幾個人一起合看一張樂譜。
題目不會有 樂譜 < 樂器種類 的情況

舉例：演奏小提琴有 8 個人、兩張樂譜，那麼小提琴 4 個人一起看一張樂譜。
題目連結

重點觀念

• 這邊可以用兩種做法，其中 Binary Search 最好實現
  • priority_queue
    priority_queue 是 heap sort 的應用，理論就是不斷拿出 heap tree 的 root，需要看 heap sort 請看大衞的筆記
  • Binary Search
    注意，這裡的二分搜尋的區間是 [L,R]，而學習連結是 [L,R)
• Udebug 的第二個測資有誤…。(在我寫這篇文章時他是第二個)

分析

• 通常大家第一個會先想到 priority_queue，但我們要考慮一種情況。
  • 舉例：p = 5, n = 3, 9,1,1
    • 如果用最簡單的做法，大到小 priority_queue 然後不斷除二，會遇到小數點的問題。
      • 9/2= 4.5，這時候就變成我們要 + 1，push(5)
      • 但正確答案其實是 3。
    • 也就是說，如果用 priority_queue 實作，我們必須用一個 struct 實作，參數有。
      • 樂手數量
      • 幾個樂譜
      • 幾個人看一張樂譜
    • 但這樣比較麻煩，因為你必須寫 struct compare。
• 二分搜尋，這個大家比較不會想到，原因是因為不直觀。
  • 想想，其實我們是要找出一種狀況是最多會有幾個人一起合看一張樂譜。
  • 題目詢問我們的是x 個人一起合看一張樂譜
  • 我們把題目想深一點，可以想成這個樂團最多 x 個人看一張樂譜，樂譜總數量有沒有超過 p
  • 這時候就可以轉化成二分搜尋，降低複雜度。我們只要找到最低的 x 就可以了！此時就不會被 p 影響，複雜度就可以降至 \(O(n \log n\)
  • 作法
    • 左邊界設為 1 個人看一張、右邊界設為樂器中最多人的一團看一張。
    • 如果再 x 個人的情況下需要 y 張樂譜
      • y 比 p 小，可以讓更多人看因此把 R 邊界降低，讓 (L+R)/2 變小，讓更少人看一張
      • y 比 p 大，把 L 邊界提高，讓更少人看一張
    • 不斷二分搜尋，找出一種最佳答案。

參考連結

Uva13177 - Orchestral scores by txya900619

心得

其實我原本是要用 priority_queue 的寫法的，只是在我想好做法後，先翻了翻解答XD。
不然假如自己程式碼寫錯還要重改很嘔嘛，又不是比賽，深思熟慮完成後對答案來改進也不差。

畢竟紙上談兵都錯了的話，那做下去也不會對。

看了後發現這題還可以用另一種方式去詮釋，覺得很棒。就寫這種做法了。

後來有在網路上看到有人用 priority_queue 這種作法，點此連結

總之，這次讓我看到了一種做法是並不是以題目給的答案為主要思考方向，而是在往上推一層，找出一個可以決定題目答案的變數，並推敲此變數已獲得答案。
這想法很不賴阿，100分。

題目程式碼

會在下面放一些簡單註解，供大家學習時參考。

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
//#define DEBUG
#define int long long
#define MAXN 100020
using namespace std;
int p, n;
int num[MAXN];

int32_t main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif // LOCAL

    while(cin >> p >> n){
        //注意：這裡我們的 m 就是分析中的 x，是要看最多 x 人拿一張樂譜的情況下，每個樂器部門需要幾張
        //左邊界設定一個人一張
        int L=1, R=0; // L 
        for(int i = 0; i < n; i++){
            cin >> num[i];
            //L = min(num[i], L);
            R = max(num[i], R); //右邊界設定以最大團的樂器部門人數數量，以此做標準拿一張
        }

        int ans = 0;
        while(L <= R){
            int mid = (L+R) / 2, required = 0; //required 總共需要幾張樂譜
            //計算每張樂譜需要的數量
            //因為每個樂團至少要一張，因此先將 mid，以避免計算出來的數字為 0
            //EX: 2 / 10 = 0，但理論上要是 1
            for(int i = 0; i < n; i++) required += (num[i] + mid - 1) / mid;
            #ifdef DEBUG
                cout << "L R required " << L << ' ' << R << ' ' << required << '\n';
            #endif // DEBUG
            if(required <= p){ //如果 required 小於等於 p，表示還可以讓更少人拿一張
                ans = mid; //以最多 mid 人為一個單位，剛好符合答案
                R = mid-1; //由於我們的邊界是 [L,R]，因此 R-1
            }
            else L = mid+1; //由於我們的邊界是 [L,R]，因此 L+1
        }
        cout << ans << '\n';
    }

    return 0;
}