【CodeForces-807C】Success Rate【二分】

【CodeForces-807C】Success Rate【二分】

Solution:

一开始按照x *q 与 y * p比较来做的,小于就x++,y++,大于就只y++,结果TLE。然后就按照最初想的,最后结果一定有x’ = kq,且y’ = kp,需要有x’ >= x,y’ >= y,枚举k试了一下,结果发现有问题,样例的3 10 1 2当k取5的时候上面不等式就已经满足了,但是这个k = 5是有问题的,发现y的增量需要保证大于等于x的增量,接着发现增量一做差就是没有通过的数量的增量,那么索性先求出y – x以及p – q,即没有通过的数量,之后再保证没有通过的和通过的数量的增量都是正的,根据这点来二分就可以了。

#include <iostream>

using namespace std;

typedef long long LL;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    LL x, y, p, q;
    cin >> t;
    while (t--) {
        LL cnt = 0;
        cin >> x >> y >> p >> q;
        if ((p == q && x != y) || (p == 0 && x != 0)) {
            cout << -1 << "\n";
            continue;
        }
        LL diff = y - x;
        LL d2 = q - p;
        LL l = 1, r = 1e9;
        while (l < r) {
            LL mid = (l + r) >> 1;
            if (mid * d2 < diff || mid * p < x) l = mid + 1;
            else r = mid;
        }
        cout << l * (q - p) - y + x + l * p - x << "\n";
    }
    return 0;
}