C 裝備合成

題意：

牛牛有{x}x件材料{a}a和{y}y件材料b，用{2}2件材料{a}a和{3}3件材料b可以合成一件裝備，用{4}4件材料{a}a和{1}1件材料b也可以合成一件裝備。牛牛想要最大化合成的裝備的數(shù)量，于是牛牛找來了你幫忙。

思路：

1.線性規(guī)劃 O(1)
這個高中知識裸題沒啥好說的畫個圖求兩直線交點，特判一下交點不在第一象限的時候取兩直線和x軸、y軸的交點的最小值即可。
坑點：線性規(guī)劃得到的最佳答案為浮點值，浮點運算精度可能出現(xiàn)問題，然后還要考慮下取整，所以可以求計算得到的值取整上下范圍的一個值，這里取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;
}