链接：https://ac.nowcoder.com/acm/contest/5505/E
来源：牛客网

 

 思路：假如我们只用第一种方法来制造装备，那么最多的装备量为：min(n/2,m/3);

　　　 那么，我们想要最大化装备数量，就是减少第一种方法的制造次数，然后用第二种方法去制造

　　　于是，我们的目的就是找到这个最优的方法。

　　　在使用x次第一种方法，y次第二种方法时，装备数量最多

　　　那么在使用小于x次的第一种方法时，从左到右为递增状态，

　　　在使用大于x次的第一种方法时，从左到右依次递减

　　　所以这是一个上凸形函数

　　　我们可以通过三分来解决这道题；

　　　于是，附上三三分模板，我在处理三分的边界问题的时候；

　　　整数方面是让其趋于一个区间大小，然后枚举这个区间内的最优值

　　　小数方面是区域某一精度

　　　这道题为整数，我们让答案区间为10，然后枚举这个区间即可

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n,m;
 4 int check(int x)
 5 {
 6     return x+min((n-2*x)/4,m-3*x);
 7 }
 8 int main()
 9 {
10     int T;
11     scanf("%d",&T);
12     while(T--){
13         scanf("%d%d",&n,&m);
14         int L=0,R=min(n/2,m/3);
15         int ans;
16         while(R>L){
17             int mid1=L+R>>1;
18             int mid2=mid1+R>>1;
19             if(check(mid1)<check(mid2)){
20                 L=mid1;
21                 ans=check(mid2);
22             }
23             else{
24                 R=mid2;
25             }
26         }
27         printf("%d\n",ans);
28     }
29     return 0;
30 }

View Code