G. Gift Set
题意：
给4个数x,y,a,b
每次可以进行2个操作
操作1 如果 x >= a , y >= b , x -= a , y -= b ;
操作2 如果 x >= b , y >= a , x -= b , y -= a ;
问最多可以进行多少次操作
(1≤x,y,a,b≤1e9)
思路：
假设操作1进行了i次，操作2进行了j次
那么可以得到
x - a * i - b * j >= 0
y - b * i - a * j >= 0
即
a * i + b * j <= x
b * i + a * j <= y
i >= 0
j >= 0
目标函数是 max(i + j)
a,b,x,y是常数
并且i,j都是整数点
这样就转换成了高中常见的线性规划的题
给定n个约束条件
求目标函数最大值
做法是求所有交点坐标
然后每个都算一遍
最后取最大值或者最小值
因为这题是整数点的原因
所以对每一个交点坐标8个方向都走1到2遍算出所有可能的整数点
然后更新答案
时间复杂度：O t
#include<bits/stdc++.h>
#define fer(i,a,b) for(re i = a ; i <= b ; ++ i)
#define re register int
#define pll pair<int,int>
#define x first
#define y second
#define sf(x) scanf("%d",&x)
#define sfl(x) scanf("%lld",&x)
typedef long long ll ;
using namespace std;
const int N = 1e6 + 10 , M = 1010 , inf = 0x3f3f3f3f , mod = 1e9 + 7 ;
int t ;
ll x , y , a , b ;
ll res = 0 ;
ll get(ll i , ll j)
{
if(a * i + b * j <= x && b * i + a * j <= y && i >= 0 && j >= 0)
return i + j ;
else return 0 ;
}
int dx[] = {1,1,-1,-1,1,-1,0,0,0} ;
int dy[] = {1,-1,1,-1,0,0,1,-1,0} ;
void xin(ll l , ll r , int u)
{
if(u == 2) return ;
/*
res = max(get(l,r),res) ;
res = max(get(l++,r),res) ;
res = max(get(l,r++),res) ;
res = max(get(l++,r++),res) ;
res = max(get(l--,r),res) ;
res = max(get(l,r--),res) ;
res = max(get(l--,r--),res) ;
res = max(get(l++,r--),res) ;
res = max(get(l--,r++),res) ;
*/
for(int i = 0 ; i < 9 ; i ++)
{
ll k1 = l + dx[i] , k2 = r + dy[i] ;
res = max(get(k1,k2),res) ;
xin(k1,k2,u + 1) ;
}
}
int main()
{
cin >> t ;
while(t--)
{
cin >> x >> y >> a >> b ;
if(a != b)
{
ll m = a * a - b * b ;
ll l = (x * a - b * y) / m ;
ll r = (a * y - x * b) / m ;
// cout << l << " " << r << "
" ;
res = 0 ;
// 对所有可能的交点坐标更新答案
xin(l,r,0) ;
xin(0,0,0) ;
xin(0ll,x/b,0);
xin(0ll,y/a,0);
xin(x/a,0ll,0);
xin(y/b,0ll,0);
cout << res << "
" ;
}
else
{
int ans = min(x,y) / a ;
if(ans < 0) ans = 0 ;
cout << ans << "
" ;
}
}
return 0;
}