[Training] GCJ 2015 Round 2 Kiddie Pool

Kiddie Pool 問題簡化如下：

n 個水龍頭 1...n，每個水龍頭出水速度 Ri，各自水溫為 Ci 。今要混合成溫度 X 且體積 V 的水，求最小時間？

1. 題目給的溫度公式，跟質心公式一樣。所以目標溫度 X，可以平移到數線 0 的位置。也就是每個水龍頭溫度都改為 X-Ci，目標改為配出溫度 0 度的水，方便計算。
2. 考慮某個水龍頭開的時間最久，開啟時間為 t 秒，則得知其他的水龍頭最多也只能開啟 t 秒，不能再多。現在的目標為 t 需最小。
3. 因此本題化簡為：假設最終答案就是 t 秒，每個水龍頭假設都先開啟 t 秒，各自裝入各自的水杯，然後計算有哪些水杯內的水是多餘的，需要倒掉。倒掉後的每杯水體積總和要逼近目標的體積 V，總和超過或小於 V，就要調整 t 的大小，直到體積總和等於 V 為止。
4. 解上述第 3 點的問題，可以想像成有一蹺蹺板，上面放著 n 杯水。每杯水重量為 Ri × t。每杯水跟支點距離 abs(X-Ci)。為了維持平衡，必須將多餘的水從某幾杯中倒出，微調到蹺蹺板平衡時，所有水杯總重量總和需逼近 V。
5. 利用貪婪演算法，從靠近支點處往遠離支點處走訪每個水杯，並累計力矩的值，左右兩邊一定會至少有一邊走訪到盡頭，此時若有一邊的力矩比較多，將力矩多的那邊當前走訪到的水杯，透過倒掉水的方式使左右平衡。
   調整到支點左右力矩相等時，檢查水的體積總和是否符合要求，如果總體積太小，就拉高 t 值，否則降低 t 值。t 值的逼近，用 Binary Search 逼近法。
6. 本題要十分注意的地方是 IMPOSSIBLE 的判斷。如果蹺蹺板支點沒有任何物品，且支點左邊全空或右邊全空，就是 IMPOSSIBLE 的情況。如果支點有物品，或者支點左右都有物品，此時 t 已經快要趨近極大，就代表 IMPOSSIBLE。

核心程式碼如下：
其中 left/right 代表支點左右的力矩，v_max 為當前 t 值下，力矩平衡的最大體積，center 是用來判斷支點有沒有物品。binary search 的 iteration 共 1000 次。

        // binary search
        double low = 0, high = 1e20;
        for(int it = 0; it < 1000; it++)
        {
            double ans = (low + high) * 0.5;
            double left = 0, right = 0, center = 0, v_max = 0, acc = 0;   // my way.
            for(int i=0; i<n; i++)
            {
                v_arr[i] = rate_arr[i]*ans;
                if(t_arr[i] < 0)       left  -= (v_arr[i]*t_arr[i]);     // this is ok.
                else if(t_arr[i] > 0)  right += (v_arr[i]*t_arr[i]);              
                else                   center += (v_arr[i]);
            }
            
            if((center == 0) && ((left==0) || (right==0)))
            {
                low = 1e20;
                break;
                // ok
            }

            if(left < right)
            {
                for(int i=0; i<n; i++)
                {
                    if(t_arr[i] > 0)
                    {
                        acc += (v_arr[i] * t_arr[i]); 
                        if(acc > left)
                        {
                            double tmp = acc - left;
                            v_max += (v_arr[i] - (tmp/t_arr[i]));
                            break;
                        }
                        else
                        {
                            v_max += v_arr[i];
                        }
                    } // if t_arr[i] > 0
                    else
                    {
                       v_max += v_arr[i];
                    }
                }
            }
            else // left >= right
            {
                for(int i=(n-1); i>=0; i--)
                {
                    if(t_arr[i] < 0)
                    {
                        acc -= (v_arr[i] * t_arr[i]); 
                        if(acc > right)
                        {
                            double tmp = acc - right;
                            v_max += (v_arr[i] + (tmp/t_arr[i]));
                            break;
                        }
                        else
                        {
                            v_max += v_arr[i];
                        }
                    } // if t_arr[i] > 0
                    else
                    {
                       v_max += v_arr[i];
                    }
                }
            }
            if(v_max > v)                   high = ans; 
            else if(v_max < v)              low  = ans;
            else                            high = low = ans;
        } 

以下是我自己出給自己的隨堂測驗跟作業：（需於 2020/01/15 前完成）

• 如果在上述第 5 項中，貪婪演算法從距離支點較遠的項目往支點方向走訪，則是否能成功解題？
  
  [Answer] 
  無法解題。
  如果從離支點較遠的地方往支點走訪，根據貪婪演算法，在水龍頭開 t 秒後用此法微調至左右平衡，最後水的總體積並不是最大體積。
  假設支點左右的總力矩，分別是 F1 和 F2，且 F1<F2。
  此時 F1 那邊的水一定都沒有被倒掉。
  F2 的水如果只倒掉靠近支點的那幾杯來取得左右力矩平衡，根據貪婪演算法，平衡後得到的總體積是 F1 那邊不倒掉水的情況下，體積的最小值 Vx。
  因此可以想像，我們有機會透過降低 t 時間，讓 F1 降低，同時找到一個相同的總體積 Vx，使左右力矩平衡。
• 用上述第 5 項的方法微調力矩到平衡時，會不會有 t 較小時，總體積反而比 t 較大時的體積還多的情況？
  
  [Answer]
  不會，支點左右的水杯在還沒倒水前裝的水最多，正比於 t 值。t 下降時，體積總和必定下降。
• 程式對於小數點以下精確度的問題，要怎麼確保？
  
  [Answer]
  採用以下方式輸出答案，9 代表小數點以下的精確位數：
  

   cout.precision(9);
   cout << fixed << ans << endl;
  

  或者：

   printf("%.9f\n", ans);
  

• 解 UVA 10498。