8.22测试总结

Luck_Deepsea · 2025-08-22 17:33:20 · 算法·理论

8.21测试总结

T638475 调酒大师

得分:0

应得:100

考点:二分

错误思路:暴力-模拟，能选2-2的方法就选它，然后再考虑1-3或3-1，使用dfs进行以上过程

正确思路:使用二分进行模拟，得出结果（因为本题具有单调性）

1.输入.
2.定义l,r(于核心代码2)
3.定义二分边界(于核心代码2)
4.判断(check函数)
5.check函数(于核心代码1)
6.输出

核心代码1：

bool check(int mid){
    if(n<mid||m<mid||m+n<mid*4)return 0;
    return 1;
}

核心代码2：

        while(l+1<r)
        {
            int mid=(l+r)/2;
            if(check(mid))
            {
                l=mid;
            }
            else
            {
                r=mid;
            }
        }

完整代码:

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
int t,maxx=0;
int n,m;
bool check(int mid){
    if(n<mid||m<mid||m+n<mid*4)return 0;//三种失败情况
    return 1;//成功
}
signed main()
{
    cin>>t;
    while(t--)//t组数据
    {
        cin>>n>>m;
        int l=0,r=n+1;//初始便捷
        while(l+1<r)//边界
        {
            int mid=(l+r)/2;//二分
            if(check(mid))//判断
            {
                l=mid;//成功:更新l
            }
            else
            {
                r=mid;失败:更新r
            }
        }
        cout<<l<<endl;//输出
    }
    return 0;//结束
}