codeforces 807 C. Success Rate（二分）

题目链接：http://codeforces.com/contest/807/problem/C

题意：记 AC 率为当前 AC 提交的数量 x / 总提交量 y 。已知最喜欢的 AC 率为 p/q (pq∈[0,1]) 。求最少在提交多少题（AC or NOT）能恰好达到 AC 率为 p/q

题解：当然可以用数学的方法来求解，我的解法并不是用什么数学方法，直接二分暴力就行。

由于(x+s)/(y+s+us)=(p/q)（s表示ac的，us表示没ac的）所以不妨设

x+s=k*p,y+s+us=k*q。

然后就是枚举k就行了。

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long ll;

int main() {

    ll t , x , y , p , q;

    cin >> t;

    while(t--) {

        cin >> x >> y >> p >> q;

        ll l = 1 , r = 1000000000;

        ll mid = (l + r) >> 1;

        while(l <= r) {

            mid = (l + r) >> 1;

            ll s = p * mid - x , tot = q * mid - y;

            //cout << s << ' ' << tot << endl;

            if(tot >= s && s >= 0) {

                r = mid - 1;

            }

            else {

                l = mid + 1;

            }

        }

        //cout << r + 1 << endl;

        if(x * q == y * p) {

            cout << 0 << endl;

        }

        else if(p == q || p == 0) {

            cout << -1 << endl;

        }

        else {

            cout << q * (r + 1) - y << endl;

        }

    }

    return 0;

}

巴特西

codeforces 807 C. Success Rate（二分）

最新文章

热门文章