【练习】装备合成

题目

题目描述：

牛牛有x件材料a和y件材料{b}b，用2件材料a和3件材料b可以合成一件装备，

用4件材料a和1件材料b也可以合成一件装备。

牛牛想要最大化合成的装备的数量，于是牛牛找来了你帮忙。

输入描述：
输入包含{t}t组数据
第一行一个整数t

接下来t行每行两个整数x,y

输出描述：
每组数据输出一行一个整数表示答案。

解析

这道题有两种写法：<1>数学题。<2>三分法。

<1>数学题：

这道题不（wo）难（mei）发现是一道线性规划的题目。所以可以用我们高中的方法来求。

所以怎么写呢？

根据题意，我们先得到他的线性方程组。（我们在这里假设第一种生产了m件，第二种生产了n件）。
---分割线---（横纵坐标为mOn）
根据方程，我们可以得出右图的三种可能性，并可以依据此判断，分类讨论出我们的答案。
首先两个单调曲线十分好求，由于我们求的是m+n的最大值。所以直接可以得到答案为截距向下取整。我们重点看相交的情况。
相交时，我们相当于要求出交点的m和n值（不过m和n要取整，所以要考虑向上或向下取整哪个大）。
所以我们就先求出该点的m值吧：此处因为求的是交点，所以可以直接将等式联立，就能得出：m = 1.0 * (4 * y - x) / 10。（此处m为浮点数）。
然后就要对m的上取整数和下取整数求出对应的n值。（这里要考虑对应的是哪条直线：我们可以看图分辨m变大或变小时，哪条曲线在边界内）
最后比较两种哪个大就好啦~（看代码）

<2>三分法：

根据题目化简，还是假设第一种生产了m件，我们用换元法可以得到：ans = m + min((x - 2m) / 4, y - 3m)。
根据三分法，我们就可以缩小该单峰区间的极值。然后缩小到一定范围之后，我们进行枚举，取出最大值就好了。

AC代码

线性规划法

#include <iostream>
#include <cmath>
using namespace std;
typedef long long ll;
//代码预处理区

template<class T>inline void read(T& res);//整型快读函数
//函数预定义区

int main() {
    int T; read(T);
    while (T--) {
        ll x, y; read(x); read(y);
        ll x1 = y, y1 = y / 3, x2 = x / 4, y2 = x / 2;
        //分别为两条直线在x，y轴上的截距
        if (x1 <= x2) printf("%lld\n", x1);
        else if (y1 >= y2) printf("%lld\n", y2);
        //两种不相交的情况
        else {
            double maxm = 1.0 * (4 * y - x) / 10;//实数的最大m
            ll m1 = floor(maxm), m2 = ceil(maxm);
            ll n1 = (x - m1 * 2) / 4, n2 = y - 3 * m2;
            //整数的最大m，和对应的最大n
            printf("%lld\n", max(m1 + n1, m2 + n2));//输出较大方案
        }
    }
    return 0;
}
template<class T>inline void read(T& res) {
    char c; T flag = 1;
    while ((c = getchar()) < '0' || c > '9')
        if (c == '-')
            flag = -1;
    res = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        res = res * 10 + c - '0';
    res *= flag;
}
//函数区

三分法

#include <iostream>
using namespace std;
//代码预处理区

int x, y;
//全局变量区

template<class T>inline void read(T& res);//整型快读函数
int F(int n) { return n + min((x - 2 * n) / 4, y - 3 * n); }
//函数预定义区

int main() {
    int T; read(T);
    while (T--) {
        read(x); read(y);
        int left = 0, right = min(x / 2, y / 3);
        while (left + 7 < right) {
            //debug(left);debug(right);
            int mid1 = left + (right - left) / 3;
            int mid2 = right - (right - left) / 3;
            if (F(mid1) < F(mid2)) left = mid1;
            else right = mid2;
        }
        int ans = 0;
        for (int i = left; i <= right; i++)
            ans = max(ans, F(i));
        printf("%d\n", ans);
    }
    return 0;
}
template<class T>inline void read(T& res) {
    char c; T flag = 1;
    while ((c = getchar()) < '0' || c > '9')
        if (c == '-')
            flag = -1;
    res = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        res = res * 10 + c - '0';
    res *= flag;
}
//函数区