Uva12190 - Electric Bill

題目大意

題目給與一個用電瓦數轉換成錢的表，並告訴我們與鄰居一起付需要多少錢以及我們與鄰居單獨付時差的錢 (A 與 B)，我們需要找出我們自己續瘀要付多少錢。

重點觀念

• 二分搜？

分析

• 先把 A 還原成總共用多少電
• 將左定為 0 ，右定為總共用的電，開始二分搜

程式題目碼

#include <algorithm>
#include <iostream>

using namespace std;

int cwh(int bill) {
    int cwh = 0;

    cwh += min(max(0, bill / 2), 100);
    bill -= 100 * 2;

    cwh += min(max(0, bill / 3), 9900);
    bill -= 9900 * 3;

    cwh += min(max(0, bill / 5), 990000);
    bill -= 990000 * 5;

    return cwh + max(0, bill / 7);
}

int bill(int cwh) {
    int bill = 0;
    bill += min(max(0, cwh * 2), 2 * 100);
    cwh -= 100;

    bill += min(max(0, cwh * 3), 3 * 9900);
    cwh -= 9900;

    bill += min(max(0, cwh * 5), 5 * 990000);
    cwh -= 990000;

    return bill + max(0, cwh * 7);
}

int main() {
    int A, B;
    while (cin >> A >> B, A | B) {
        int total = cwh(A), ans = 0;
        int l = 0, r = total;

        while (l < r) {
            int m = (l + r) / 2;
            int diff = bill(total - m) - bill(m);

            if (diff > B) {
                l = m;
            } else if (diff < B) {
                r = m;
            } else {
                cout << bill(m) << endl;
                break;
            }
        }
    }

    return 0;
}