题解 | #游游的you矩阵#

C题用二分答案. 令 s = b-a; 题意是若s能落在[l,r],[2* l,2* r],[3* l,3* r],.....,[k*l,k *r] (k是非负整数)的某个区间中,就有解,否则无解,只需要两次二分枚举k,一次枚举最大k,一次枚举最小k,即可求解.

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int inf = 1e9 + 10;
const int N = 1e6 + 10;
const int mod = 998244353;
int n,m,k,w[N],ans;
map<int,int >mp,ap;
void solve() {
	int a,b,l,r;
	cin>>a>>b>>l>>r;
	int s = b - a;
	int mmax = INT_MIN,mmin = INT_MAX;
	int tl = 0,tr = 1e9;
	while(tr>=tl) {
		int mid = tl + tr >> 1;
		if(mid*l>s)tr = mid - 1;//s小于所枚举区间的左边界,k太大了,要缩小k
		else if(r*mid<s)tl = mid+1;//
		else {
			mmax = mid;
			tl = mid+1;//找的是最大k,找到后mmax记录答案,然后再往右边找
		}
	}
	tl = 0,tr = 1e9;
	while(tr>=tl) {
		int mid = tl + tr >> 1;
		if(mid*l>s)tr = mid-1;
		else if(r*mid<s)tl = mid+1;
		else {
			mmin = mid;
			tr = mid-1;
		}
	}
	if(mmin==INT_MAX||mmax==INT_MIN)cout<<-1<<endl;
	else cout<<mmin<<" "<<mmax<<endl;
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int T = 1;
	cin>>T;;
	while(T--) {
		solve();
	}

}