UVa12190 - Electric Bill(Binary Search 二分搜尋 )

題目大意

在 2100 年，電變得非常昂貴，電力公司的累進費率如下

• 1~10CHw 2元
• 101~10000 3元
• 10001~1000000 5元
• 1000000 7元

電力公司為了賺更多錢想出一種方法，電力公司會給你 A、B 兩個數字，其中

• A 是你的用電量與鄰居用電量的總和，如果合在一起的電費帳單
• B 是你的電費與鄰居電費的差額

如果想知道自己的電費，則必須付給電力公司計算費，但你想要省下這筆錢，所以來寫程式計算八！
我們可以保證的是，我們一定比鄰居的用電量還少！
注意：在這題中，每組題目都答案只會有一組解。不必擔心多組解問題

題目連結

重點觀念

• 如何計算電費
• 如何找出 鄰居、你 的用電量
• 想到使用二分搜尋來找出鄰居、你的用電量
• 在有兩種未知數，並且有一定的線性規律時可以透過二分搜尋來確認此未知數。

分析

我們可以透過一些簡單的數學公式找出一些邏輯，定義我的帳單是 billA 用電量為 chwA、鄰居的帳單是 billB、用電量是 chwB。
加上題目 A、B

• 用 A 推出 (chwA + chwB)，總和的電費我們稱為 chwAll
• 再來我們要如何推出我們的電費、鄰居的電費呢？

由於我們知道 B，但是現在我們還是有兩個未知數 chwA、chwB 阿，我們總不能夠用 for(int chwA = 0; i < chwAll; i++)，再讓 chwAll - chwA 推出 chwB 後，再用 chwA、chwB 計算帳單費用，比較差額是否與 B 相同。

但是我們可以做些小優化，我們知道，如果 chwA、chwB 越相近，則電費差額會越低，如果越遠則電費差額會越高。
那我們原本是用 for 一個一個慢慢找，可不可以改成用二分搜尋，只要電費差額 > B，我們就讓鄰居跟我們的電費差額變小，直到完全一樣。
如果電費差額 < B，那我們就讓電費差額變大，直到完全一樣。

當然，偶爾會有變大又變小的時候，畢竟二分搜尋有可能不小心變更大嘛。

如果不懂二分搜尋，可以參考此文章演算法知識 - Binary Search 二分搜尋 by 大衛的筆記

參考連結

Uva12190 - Electric Bill by txya900619

心得

QQ，我再搞清楚這題為甚麼要用二分搜尋時花了一堆時間…，有時候想要用數學去推論一題的 UVa 並不是那麼容易的事情呀，唉。

現在大概清楚，在哪些狀況怎麼做比較好！

我的功力還不足，還需要繼續努力。

還有就是，我的英文真的好菜阿！需要找時間好好多準備英文單字，讓自己的英文能力變得更強，閱讀更快！

題目程式碼

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

#include <iostream>
#include <bits/stdc++.h>
#define int long long
#define LOCAL
using namespace std;
const int MAXN_quota = 1e18; //最終的額度，由於題目限度是 1e9
int price[] = {2,3,5,7}; //電的價格分類
int quota[] = {100,9900,990000, MAXN_quota}; //電的額度分類
int a, b;

int bill_convert_to_cwh(int bill){ //電價轉換成用電量
    int chw = 0;
    for(int i = 0; i < 4; i++){ 
        if(bill > 0){ //如果帳單還沒有歸零
            //判斷在當前的價格中，是剩下的帳單費用 / 當前價格是否有將額度用完，
            //如果有，那讓用電家 += 額度
            //如果沒，就讓用電量 += 帳單費用 / 當前用電量
            chw += min(bill/price[i], quota[i]); //紀錄在這個費用下，增加多少的用電量
            
            //帳單扣掉在此額度下用掉的費用
            bill -= min(bill/price[i], quota[i]) * price[i];  
            //cout << "now_bill " << bill << '\n';
        }
    }
    return chw; //回傳用電量
}

int chw_convert_to_bill(int chw){ //用電量轉換帳單
    int bill = 0; 
    for(int i = 0; i < 4; i++){
        if(chw > 0){ //還有用電量
            //判斷在當前的價格中，是剩下的用電量是否有將額度用完，
            //如果有，那讓價格 * 額度
            //如果沒，就讓用電量 * 額度
            bill += min(chw, quota[i]) * price[i]; 

            //用電量扣掉在此額度下用掉的電量
            chw -= min(chw, quota[i]);
            //cout << "now_chw " << chw << '\n';
        }
    }
    return bill; //回傳電量
}

//如果不懂，可以看 演算法知識 - Binary Search 二分搜尋 by 大衛的筆記，在分析的最下方。
int binary_serach(int chw){ //二分搜尋，找出 billB - billA = B
    int billA, billB;
    int left=0, right=chw; //chw 總用電量

    while(right > left){ //二分搜尋
        int mid = (left + right) / 2;
        billA = chw_convert_to_bill(mid); 
        billB = chw_convert_to_bill(chw - mid);
        //cout << "bill " << billA << ' ' << billB << '\n';

        int diff = billB - billA; //找出差額
        if(diff == b) break; //如果差額 == b，表示找到答案
        if(diff < b) right = mid; //如果差額小於 b，則表示要找右區間、擴大差額
        if(diff > b) left = mid+1; //如果差額大於 b，則表示要找左區間、縮小差額
    }
    return billA; //回傳帳單
}

int32_t main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif // LOCAL
    int chwAll, chwA;
    while(cin >> a >> b && a+b != 0){
        chwAll = bill_convert_to_cwh(a); //找出總店輛
        //cout << chwAll << '\n';
        int chwA = binary_serach(chwAll); //進行二分搜尋
        cout << chwA << '\n'; //輸出我們的用電量
        //cout << chw_convert_to_bill(chwA) << '\n';
    }
    return 0;
}