CF773A Success Rate 题解

Success Rate

(提供二分做法)

前言

听说是史上最简单蓝题,做了一下。

题意

已知 x,y,p,qx,y,p,q,通过只让 yy11x,yx,y 同时加 11,使得满足:

xy=pq \frac{x'}{y'}=\frac{p}{q}

思考

目标状态为 pq\frac{p}{q},考虑到这是个比值,自然 xy=kpkp\frac{x’}{y’}=\frac{kp}{kp}
明显地,这里的 kk 如果合法,那就一定有更小的 kk

所以考虑二分。

限制条件呢?

因为无论如何决策,yy 都会加 11;而 xx 不一定每一次决策都加 11。即 ΔyΔx\Delta y\geq \Delta x

所以保证 ΔxΔy\Delta x \leq \Delta y 就好了。即 kpxkqykp-x\leq kq-y

需要注意的是,有一点需要特判:

  • p=0p=0
    • x>0x> 0,输出 1-1
    • x=0x=0,输出 00

代码

考虑到数据范围均小于 10910^9,所以右端点不可以取太大,否则越界变成负数,右端点取 101010^{10},开个 long long 就好了。

code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<bits/stdc++.h>
using namespace std;

#define int long long

int x,y,p,q;

bool check(int md)
{
    return p*md-x<=q*md-y && p*md>=x;
}

void solve()
{
    scanf("%lld%lld%lld%lld",&x,&y,&p,&q);
    if(p==0)
    {
        if(x)
            puts("-1");
        else
            puts("0");
        return;
    }

    int l=1,r=1e10,mid,ans=-1;
    while(l<=r)
    {
        mid=l+r>>1;
        if(check(mid))
            r=mid-1,ans=mid;
        else
            l=mid+1;
    }
    
    if(ans==-1)
        puts("-1");
    else
        printf("%lld\n",ans*q-y);
}

signed main()
{
    signed T;
    scanf("%d",&T);
    while(T--)
        solve();
    return 0;
}
Licensed under CC BY-NC-SA 4.0