g647 - Error
題目描述
題目要求找到兩個非負整數 ansx 和 ansy，使得 x * ansx + xx * ansy >= v 且 y * ansx + yy * ansy >= v，並最小化 ansx + ansy。
解題思路
這題的核心在於尋找滿足兩個不等式的最小 ansx + ansy。由於題目沒有給出明確的範圍，直接暴力枚舉不可行。可以利用二分搜尋法來尋找最小的 ansx + ansy 值。
首先，二分搜尋的範圍需要確定。由於 ansx 和 ansy 都是非負整數，且需要滿足兩個不等式，因此可以設定二分搜尋的範圍為 [0, 2 * v]。
在二分搜尋的過程中，對於每個中間值 m = ansx + ansy，需要判斷是否存在 ansx 和 ansy 使得 ansx + ansy = m 且滿足兩個不等式。判斷的方法是枚舉 ansx 的值，然後計算 ansy = m - ansx，並檢查是否滿足兩個不等式。
找到滿足條件的最小 m 後，再回溯尋找對應的 ansx 和 ansy。
複雜度分析
- 時間複雜度: O(T * V * log(2V))，其中 T 是測試案例數量，V 是題目給定的 v 值。二分搜尋的範圍是 2V，每次二分搜尋需要 O(V) 的時間來判斷是否存在滿足條件的 ansx 和 ansy。
- 空間複雜度: O(1)，程式碼只使用了常數級別的額外空間。
程式碼
#include <iostream>
using namespace std;
long long t,x,y,xx,yy,v,ansx,ansy;
bool judge(long long n){
for(long long i=0;i<=n;++i){
if(x*i+xx*(n-i)>=v&&y*i+yy*(n-i)>=v)return 1;
}
return 0;
}
long long bs(long long l,long long r){
if(l>r)return l;
long long m=(l+r)/2;
if(judge(m)){
bs(l,m-1);
}
else{
bs(m+1,r);
}
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> t;
while(t--){
cin >> x >> y >> xx >> yy >> v;
//100000 1 100000 1 100000
long long mi=bs(0,v*2);
ansx=ansy=0;
for(long long i=0;i<=mi;++i){
if(x*i+xx*(mi-i)>=v&&y*i+yy*(mi-i)>=v){
ansx=i;
ansy=mi-i;
break;
}
}
cout << ansx << " " << ansy << "\n";
}
}