ProblemH High Load Database (Complex Optimization)

題目大意：

給你兩組陣列 (定義為 A , B)，詢問 B 的每一個數字，能將 A 分割最大。
補述說明：　可將 A 想像成包裹 B 想像為箱子
要將 A 塞到 B 裡面並最佳化利用但必須按照順序，試問需要幾個箱子。

分析：

這題看起來很簡單對不對！
但其實它是非常可怕的效率優化
要是打得像文章一樣，沒人會理解吧！

1. 使用前綴和 + 二分收尋
   在上一份包裹沒被收納前，下一份包裹就無法加入箱子。並且透過二分收尋的方式，就可以很方便的加入並且省掉撰寫更多程式碼的時間。

   舉例:
   EX: 2 2 4 3 3 包裹 => 2 4 8 11 14 設定箱子為 4
   因此一開始收尋 4 是在 4 8 之間 (這裡使用 C++ upper_bound 直接抓 > x 的值 index)，因為 4+4 = 8 ，因此我下次就收尋 8，8 在 8 13 之間，所以 8+4 = 12，以此類推。每做二分收尋一次就是多切一段，很聰明的想法吧！只是單單這樣還是不夠的，俄羅斯沒那麼友善QQ。

2. 找出包裹之間的最大值並與箱子比較
   這想法其實一開始我的隊友跟我說時，我還無法想通邏輯。但多思考個幾分鐘就能懂了，我的邏輯敏感力還是不太好啊…。

   假設題型：
   如果 箱子是 5 ，包裹為 3 6 7 8 9，那箱子 5 是不是必定沒辦法包住 6 7 8 9? 因此我找出這些包裹的最大差額，要是箱子不能裝到裡面最大的包裹，就直接判斷 Impossible，省去 step1 的查找時間。反正有找跟沒找還不是一樣

3. 他的查找資料是會重複的
   最機車的地方
   應該是我英文底子不太好，可能看不太懂他有說資料會重複查詢抑或是他沒有說。這邊我是去查看這邊我是去查看Little_Fall 天才，不然我應該永遠都想不出來吧…。
   好了，前面廢話那麼多，該講重點了。再新增一個陣列來記錄如果使用 t 箱子可以裝幾個包裹就可以完成了！

這份解題記錄我打了一小時…好累阿。還有兩題要打，加油!

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
using namespace std;
int arr[200020] = {} ;
int save[1000200] = {} ;

int main()
{
#ifdef LOCAL
    freopen("in1.txt" , "r" , stdin );
#endif // LOCAL
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n , sum =0 , Mv = 0 ;
    cin >> n ;
    for(int i = 0 ; i < n ; i++){ //cin array
        cin >> arr[i] ;
        sum += arr[i] ;
        arr[i] = sum ;
        Mv = max(Mv, arr[i] - arr[i-1]);
    }

    memset(save , -1 , sizeof(save));
    int seaT , t , seaN , index ;
    cin >> seaN ;
    for(int i = 0 ; i < seaN ; i++){
        cin >> t ;
        seaT = t ;
        sum = 0 ;
        index = 0 ;
        int flag = 0; //flag = 1 non-impossible flag2 = impossible

        if(save[t] != -1)
            flag = 1 ;

        if(Mv > t)
            flag = 2 ;

        while(flag==0){
            index = upper_bound(arr+index , arr+n , seaT )-arr;

            //debug
            //cout << "seaT=" << " " << seaT << " value=" << arr[index-1] << '\n' ;

            if(index == n){ 
                flag = 1;
                save[t] = ++sum ;
                break;
            }
            seaT = arr[index-1] + t ;
            sum++ ;
        }
        if(flag == 2 || save[t] == 0 )
            cout << "Impossible" ;
        else{
            cout << save[t] ;

        }
        cout << '\n' ;
    }



    return 0;
}