C 装备合成

题意：

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

思路：

1.线性规划 O(1)
这个高中知识裸题没啥好说的画个图求两直线交点，特判一下交点不在第一象限的时候取两直线和x轴、y轴的交点的最小值即可。
坑点：线性规划得到的最佳答案为浮点值，浮点运算精度可能出现问题，然后还要考虑下取整，所以可以求计算得到的值取整上下范围的一个值，这里取1即可，不过为了保险起见开大点开个10也是没问题的。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;

ll a,b,res;

void f(ll m){
    for(ll i=m-1;i<=m+1;i++){
        ll n=min((a-2*i)/4,b-3*i);
        if(i>=0&&n>=0&&(2*i+4*n)<=a&&(3*i+n)<=b) res=max(res,i+n);
    }
}

int main(){
    ll T;
    cin>>T;
    while(T--){
        res=0;
        cin>>a>>b;
        double x=(4.0*b-1.0*a)/10.0;
        f(x);
        f(0);
        f(min(a/2,b/3));
        cout<<res<<'\n';
    }
    return 0;
}

2.三分法 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;

ll x,y;
ll res;

ll check(ll m){
    ll n=min((x-2*m)/4,y-3*m);
    res=max(res,n+m);
    cout<<"m="<<m<<"  n="<<n<<'\n';
    return n+m;
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;cin>>T;
    while(T--){
        res=0;
        cin>>x>>y;
        ll L=0,R=min(x/2,y/3);
        while(R-L>10){
            ll m1=L+(R-L)/3;
            ll m2=R-(R-L)/3;
            if(check(m1)<check(m2)){
                L=m1;
            }else{
                R=m2;
            }
        }
        for(int i=L;i<=R;i++){
            check(i);
        }
        cout<<res<<'\n';
    }
    return 0;
}