题解 | #装备合成#

修补骑士一开始又想写DP了，这是个什么完全二维背包DP，看着都抽象。并且可能会有TLE，MLE的问题

但是，这道题的思路让我想起了NC15446（同样也被我当成了背包）

单次判断的核心在于：我们只关心于是否存在合规的情况，虽然这个情况很可能不是最终答案

但至少说明了存在就行，我们继续二分下去，最后的情况就是“存在合规，并且只有这一个合规”，而不是用DP直接尝试找出所有选择方案当中的最佳。这种看上去很像是用DP找出最好情况的题如果能找到二分关系（这里是装备数量与材料数量，一定是负贡献的），就可以“只管有没有”，二分压缩到最后的情况就是题解！

顺带一提这题里有个陷阱：就是我们要max(4 * mid - x,0)，min(y - mid,2 * mid)，因为单个方案数量（假设k）肯定是在mid与0之间的（我一开始忘记了这第三个限制条件结构全WA了，这数据还怪严谨的（？））

AC代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;

bool check(int mid,int x,int y)
{
    int left = 4 * mid - x; 
    
    if(left < 0)
    {
        left = 0;
    }
    
    int right = min(y - mid,2 * mid);
    
    if(left < right || (left == right) && left % 2 == 0)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}

signed main() 
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
    int T; 
    
    cin >> T;
    
    for(int r = 0;r < T;r++)
    {
        int x,y;
        
        cin>>x>>y;

        int left = 0,right = min(x,y);
        
        int ans = 0;//对于二分，ans更有优势能处理更多情况（？）
        
        while(left <= right)
        {
            int mid = (left + right)/2;
            
            if(check(mid,x,y))
            {
                ans = mid;
                
                left = mid + 1;//太小了，可以变大
            }
            else
            {
                right = mid - 1;
            }
        }
        
        cout<<ans<<endl;
    }
    
    return 0;
}