牛客练习赛 59 C. 装备合成

发表于 更新于 分类于

链接

https://ac.nowcoder.com/acm/contest/4743/C

题意

$A$ 有 $x$ 个，$B$ 有 $y$ 个

$2$ 个物品 $A$ 和 $3$ 个物品 $B$ 可以合成一件装备

$4$ 个物品 $A$ 和 $1$ 个物品 $B$ 可以合成一件装备

求最多可以合成多少件装备

思路

三分

设用第一种方法合成的装备为 $n$ 件，那么总共合成的装备为：$n+min((x-2n)/4,y-3n)$

通过打表发现这是个单峰函数

因此用三分寻找极值即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;
int x,y;
int cal(int p) {
    return p+min((x-2*p)/4,y-3*p);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;cin>>T;
    while(T--) {
        cin>>x>>y;
        int l=0,r=min(x/2,y/3);
        while(l<r) {
            int lmid=l+(r-l)/3,rmid=r-(r-l)/3;
            if(cal(l+mid)>cal(r-mid)) r=rmid-1;
            else l=lmid+1;
        }
        cout<<cal(l)<<'\n';
    }
    return 0;
}