首页 > 代码库 > codeforce C. Success Rate
codeforce C. Success Rate
写完这道题目才发现自己对二分的理解太浅了 这题是典型的利用二分“假定一个问题可行并求最优解”
二分是通过不断缩小区间来缩小解的范围，最终得出解的算法 我们定义一个c(x) 表示判断函数
如果对任意y>=x 当x满足条件的时候 y也满足条件 那么我们就一个不断缩小区间范围来确定最后的解
好扯了这么多犊子 来说下这道题目。。
我们的目的是对A,B 有 （x+A）/(y+B) == (p/q) 其中A<=B
那么可以转换为 A+x=k*p B+y=k*q;
既 A=k*p-x, B=k*q-y;（A>=0,B>=0）
这里可以验证 对任意k >= x 当x满足条件的时候 k也满足条件（自己模拟一下就知道了）
ok 二分开搞
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <map>
#include <stack>
#include <algorithm>
#include <queue>
#include <string>
#include <cmath>
using namespace std;
const int inf=1000000000;
int main()
{
int t;
cin>>t;
long long int x,y,p,q;
while(t--)
{
cin>>x>>y>>p>>q;
long long int temp=-1;
long long int l=1;
long long int r=inf;
while(l <= r)
{
long long int mid=(l+r)/2;
long long int A=mid*p-x;
long long int B=mid*q-y;
if(A>=0 && B>=0 && A<=B)
{
temp=mid;
r=mid-1;
}
else l=mid+1;
}
if(temp==-1) cout<<"-1"<<endl;
else cout<<temp*q-y<<endl;
}
return 0;
}
codeforce C. Success Rate
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。