首页 > 代码库 > Codeforces 807C - Success Rate

Codeforces 807C - Success Rate

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

题目大意:给你T组数据,每组有x,y,p,q四个数,x/y是你当前提交正确率,让你求出最少需要再提交几次可以达到目标正确率p/q;

解题思路:假设提交B次,正确A次,那么可以得到(x+A)/(y+B)=p/q,可以推出x+A=k*p,y+B=k*q.那么A=k*p-A,B=K*q-A;

     这样我们只需要二分枚举k,判断A,B是否满足(0<=A<=B)即可。

 1 #include<iostream>
 2 #include<cstdio> 
 3 using namespace std;
 4 typedef long long LL;
 5 
 6 int main(){
 7     int T;
 8     cin>>T;
 9     while(T--){
10         LL x,y,p,q;
11         cin>>x>>y>>p>>q;
12         LL l=0,r=1e10,mid;
13         LL ans=1<<30;
14         while(l<=r){
15             mid=(l+r)/2; 
16             LL A=mid*p-x;
17             LL B=mid*q-y;
18             if(A>=0&&B>=0&&A<=B){//判断是否满足(0<=A<=B) 
19                 ans=min(ans,mid);
20                 r=mid-1;
21             } 
22             else
23                 l=mid+1;
24         }
25         if(ans!=1<<30)
26             cout<<ans*q-y<<endl; 
27         else
28             cout<<"-1"<<endl;
29     }
30     return 0;
31 }

 

Codeforces 807C - Success Rate