NC200211 装备合成
题目
题目描述
牛牛有 \({x}\) 件材料 \({a}\) 和 \({y}\) 件材料 \({b}\) ，用 \({2}\) 件材料 \({a}\) 和 \({3}\) 件材料 \({b}\) 可以合成一件装备，用 \({4}\) 件材料 \({a}\) 和 \({1}\) 件材料 \({b}\) 也可以合成一件装备。牛牛想要最大化合成的装备的数量，于是牛牛找来了你帮忙。
输入描述
输入包含 \({t}\) 组数据
第一行一个整数 \({t}\)
接下来 \({t}\) 行每行两个整数 \({x,y}\)
输出描述
每组数据输出一行一个整数表示答案。
示例1
输入
5
4 8
7 6
8 10
100 4555
45465 24124
输出
2
2
3
50
13917
备注
\({1<=t<=10000}\)
\({1<=x,y<=1e9}\)
题解
思路
方法一
知识点：数学（线性规划）。
设第一种方案做了 \(m\) 件装备，第二种方案做了 \(n\) 件装备，有如下不等式
\[\begin{equation}
\left\{
\begin{array}{lr}
2m+4n &\leq x\\
3m+n &\leq y\\
m,n & \geq 0
\end{array}
\right.
\end{equation}
\]
使用线性规划方法，会得到三种可能图像：
- 两直线交点横坐标小于 \(0\) ，即 \(-x+4y < 0\) ，此时答案就是 \(y\) 。
两直线交点纵坐标小于 \(0\) ，即 \(3x-2y < 0\) ，此时答案就是 \(\lfloor \frac{x}{2} \rfloor\) 。
两直线交点在第一象限，则确定交点横坐标，分别取上下整对应函数计算纵坐标，取横纵坐标之和最大值。
时间复杂度 \(O(1)\)
空间复杂度 \(O(1)\)
方法二
知识点：三分。
设第一种方案做了 \(m\) 件装备，则根据不等式：
\[\begin{equation}
\left\{
\begin{array}{lr}
2m+4n &\leq x\\
3m+n &\leq y\\
m,n & \geq 0
\end{array}
\right.
\end{equation}
\]
有如下等式：
\[ans = m + min(\lfloor \frac{x - 2m}{4} \rfloor, y - 3m)
\]
显然是单调函数，有单峰，考虑三分。根据不等式得到 \(l = 0 , r = \min(\lfloor \frac{x}{2} \rfloor,\lfloor \frac{y}{3} \rfloor)\) 。
三分要注意写法，mid1 = l + (r-l)/3 以及 mid2 = r - (r-l)/3 ，必须是两边，以防因为当 (r - l) / 3 = 0 时，会持续移动左边界，越过峰or谷导致出错。个人喜欢下面这种写法：
int l = start,r = end;
while(l<=r){//单峰函数三分
int mid1 = l + (r-l)/3;
int mid2 = r - (r-l)/3;
if(calc(mid1)<=calc(mid2)) l = mid1 + 1;
else r = mid2 - 1;
}
//最终答案是 l-1 或者 r(不一定,要注意具体意义)
最后输出得到的点代入值。
时间复杂度 \(O(\log ( \min(\lfloor \frac{x}{2} \rfloor,\lfloor \frac{y}{3} \rfloor))\)
空间复杂度 \(O(1)\)
代码
方法一
#include <bits/stdc++.h>
#define ll long long
using namespace std;
bool solve() {
ll x, y;
cin >> x >> y;
if (-x + 4 * y < 0) cout << y << '\n';
else if (3 * x - 2 * y < 0) cout << x / 2 << '\n';
else {
int m1 = (-x + 4 * y) / 10, m2 = (-x + 4 * y + 9) / 10;///不能确定去上整还是下整更优，那就都来一遍
cout << max(m1 + (x - 2 * m1) / 4, m2 + y - 3 * m2) << '\n';///记得上下正对应不同函数
//int m = (-x + 4LL * y + 5) / 10;///玄学四舍五入居然也能过
//cout << m + min((x - 2 * m) / 4, y - 3 * m) << '\n'; ///不知道用哪个函数，但n被最小的那个限制，这么写就行
}
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}
方法二
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int x, y;
bool check(int mid1, int mid2) {
int ans1 = mid1 + min((x - 2 * mid1) / 4, y - 3 * mid1);
int ans2 = mid2 + min((x - 2 * mid2) / 4, y - 3 * mid2);
return ans1 <= ans2;
}
bool solve() {
cin >> x >> y;
int l = 0, r = min(x / 2, y / 3);
while (l <= r) {///三分m
int mid1 = l + (r - l) / 3;
int mid2 = r - (r - l) / 3;///不能l+2*(r-l)/3
//!这个很关键，因为当(r - l) / 3 = 0 时，会持续移动左边界，越过峰or谷
//!改成r - (r - l) / 3，在r-l<=2时会退化成r，也就是之后不足三分直接让l和r两点比较谁大，相当于枚举
if (check(mid1, mid2)) l = mid1 + 1;
else r = mid2 - 1;
}
cout << r + min((x - 2 * r) / 4, y - 3 * r) << '\n';
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}
