二分、非线性规划

题意：

牛牛有{x}x件材料{a}a和{y}y件材料{b}b，用{2}2件材料{a}a和{3}3件材料{b}b可以合成一件装备，用{4}4件材料{a}a和{1}1件材料{b}b也可以合成一件装备。牛牛想要最大化合成的装备的数量，于是牛牛找来了你帮忙。

分析

看到最大化想要用二分法解决，答案范围也已知，且答案具有单调性。即如果不能合成n件装备那也一定不能合成
n件以上的装备。

构建一个函数 int solve(int x,int y) 返回x件a物品，y件b物品下最多合成的装备个数。
初始化l = 0,r = 1e9
取mid = (l+r)>>1 如果能合成mid或mid以上的装备，让l = mid+1
反之令r = mid-1
最终答案一定会是l-1

那么问题的关键是如何判断是否能合成mid或mid件以上的装备呢？
假设我们要合成mid件装备
合成k件2a3b的，mid-k件4a1b的
则总消耗材料为：
k(2a + 3b) + (mid - k)(4a + b)
化简为： (4mid - 2k)a + (mid + 2k)b
那么对于这个式子就有一定要满足：

0 <= 4mid - 2k <= x
0 <= mid + 2k <= y
0 <= k <= mid（最初的条件）

我们对这三个式子进行一些合并会得到：

4mid - x <= 2k <= 2mid
0 <= 2k <= y - mid

则我们只要保证有k存在使其满足这个式子，那么就可以合成mid件装备！

如何满足呢我们令 tmp1 = max(4mid-x,0) tmp2 = min(2mid,y-mid)
那么只要存在 tmp1 <= 2k <= tmp2 的k 即可。
注意在这里因为k是整数，所以2k是偶数，因此
当tmp1==tmp2时如果tmp1为奇数式子也是不成立的！！！
当tmp1<tmp2时一定成立

代码如下，注意细节

#include<iostream>;
#include<algorithm>;
using namespace std;
typedef long long ll;
const ll max_r = 1e9 + 100;
ll x, y;

int solve(ll x,ll y) {
    ll l = 0;ll r = max_r;
    while (l <= r) {
        ll mid = (l + r) >> 1;
        ll tmp1 = min(2 * mid, y - mid);
        ll tmp2 = max(4 * mid - x, (ll)0);
        if (tmp1 == tmp2 && (tmp1&1))
            r = mid - 1;
        else if (tmp1 >= tmp2)
            l = mid + 1;
        else r = mid - 1;
    }return l - 1;
}

int main() {
    ios::sync_with_stdio(0);
    int t;cin >> t;
    while (t--) {
        cin >> x >> y;
        cout << solve(x, y) << endl;
    }
}

装备合成

二分、非线性规划

题意：

分析