装备合成(三分）

装备合成

比赛主页
我的提交

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

牛牛有xx件材料aa和yy件材料bb，用22件材料aa和33件材料bb可以合成一件装备，用44件材料aa和11件材料bb也可以合成一件装备。牛牛想要最大化合成的装备的数量，于是牛牛找来了你帮忙。

输入描述:

输入包含tt组数据
第一行一个整数tt
接下来tt行每行两个整数x,yx,y

输出描述:

每组数据输出一行一个整数表示答案。

示例1

输入

复制

5
4 8
7 6
8 10
100 4555
45465 24124

输出

复制

备注:

1<=t<=100001<=t<=10000

1<=x,y<=1e91<=x,y<=1e9

因为存在单调性极值所以可以用三分优化

//#include 
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long  ll;
#define ull unsigned long long
#define scf(n) scanf("%d",&n)
#define scfl(n) scanf("%lld",&n)
#define prf(n) printf("%d",n)
#define prfl(n) printf("%lld",n)
#define scfd(n) scanf("%lf",&n)
#define prfd(n) printf("%.lf",n)
#define prf10(n) printf("%.10f",n)
#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid (l+r)/2
#define mms(x, y) memset(x, y, sizeof x)
#define over(i,s,t) for(register long long i=s;i<=t;++i)
#define lver(i,t,s) for(register long long i=t;i>=s;--i)
const int MAXN = 305;
const int INF = 0x3f3f3f3f;
const int N=5e4+7;
const int maxn=1e5+5;
const double EPS=1e-10;
const double Pi=3.1415926535897;
//inline double max(double a,double b){
//    return a>b?a:b;
//}
//inline double min(double a,double b){
//    return a'9') {if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') {x=(x<<1)+(x<<3)+c-'0';c=getchar();}
    return x*f;
}
int xd[8] = {0, 1, 0, -1, 1, 1, -1, -1};
int yd[8] = {1, 0, -1, 0, -1, 1, -1, 1};
 
//fastPow
int fastPow(int x,int n){
    if(n==1) return x;
    int tmp=fastPow(x,n/2); //fenzi
    if(n%2==1) return tmp*tmp*x;
    else return tmp*tmp;
}
ll gcd(ll m, ll n){return n == 0 ? m : gcd(n, m%n);}
ll lcm(ll m, ll n){return m*n / gcd(m, n);}
ll pows(ll base, ll power,ll mod){ll result=1;while(power>0){if(power&1){result=result*base%mod;}power>>=1;base=(base*base)%mod;}return result;}
 
ll poww(ll base, ll power){ll result=1;while(power>0){if(power&1){result=result*base;}power>>=1;base=(base*base);}return result;}


//dijsktra
//start
//const int MAX= 10020;
//struct node {
//    int x,to,next,w;
//    bool operator <(const node &a) const{
//        return this->w>a.w;
//    }
//}G[MAX<<1];
//int cnt;
//int dis[MAX];
//int vis[MAX];
//int head[MAX];
//
//
//int m,n;
//int b[10020];
//
//
//void add(int u,int v,int w){
//    G[++cnt].to=v;
//    G[cnt].w=w;
//    G[cnt].next=head[u];
//    head[u]=cnt;
//}
//int  dijkstra(int s){
//    mms(dis,INF);
//    dis[s]=0;
//    priority_queue p;
//    node t;
//    t.x=s;
//    t.w=0;
//    p.push(t);
//    while (!p.empty()) {
//        node u=p.top();
//        p.pop();
//        int v=u.x;
//        if(dis[v]!=u.w) continue;
//        for(int i=head[v];i;i=G[i].next){
//            int to=G[i].to;
//            if(dis[to]>dis[v]+G[i].w){
//                dis[to]=dis[v]+G[i].w;
//                t.x=to;
//                t.w=dis[to];
//                p.push(t);
//            }
//
//        }
//    }
//    int m1=-1;
//        int m2=-1;
//        dis[s]=-3;
//        for(int i=1;i<=n;i++){
//            if(dis[i]==INF) continue;
//            if(dis[i]>m1){
//                m2=m1;
//                m1=dis[i];
//            }
//            else if(dis[i]>m2){
//                m2=dis[i];
//            }
//        }
//        if(m1!=-1&&m2!=-1) return m1+m2;
//        return -1;
//
//}
//
//
//int main(){
//    int t;
//    cin>>t;
//    while (t--) {
//        cin>>n>>m;
//        int u,v,w;
//
//        for(int i=1;i<=m;i++){
//            cin>>u>>v>>w;
//            add(u,v,w);
//            add(v,u,w);
//        }
//        int ans=0;
//        int cnt=0;
//        for(int i=1;i<=n;i++){
//            ans=max(ans,dijkstra(i));
//        }
//        cout<=10) str+=x%y+'A'-10;
//        else str+=x%y+'0';
//        x/=y;
//    }
//    reverse(str.begin(),str.end());
//    return str;
//}
//
//
//const int MAX=1000005;
//char str[MAX];
//char pattern[MAX];
//int cnt;
//int Next[MAX];
//void  getnext(string p,int plen){
//    Next[0]=0;
//    Next[1]=0;
//    for(int i=1;i>n;
//    string t;
//    string s="";
//    for(int i=2;i<=16;i++){
//        s="";
//        s+=work(n,i);
//        if(kmp(s,t))
//        {
//            cout<<"yes";
//            return 0;
//        }
//    }
//    cout<<"no"<>s1;
//    s2="cocacola";
//    int ans;
//    for(int i=0;i>n;
//    for(int i=1;i<=n;i++){
//        cin>>a[i];
//    }
//    //start
//    int block=sqrt(n);
//    int t=n/block;
//    if(n%block) t++;
//    for(int i=1;i<=t;i++){
//        st[i]=(i-1)*block+1;
//        ed[i]=i*block;
//    }
//    ed[t]=n;
//    for(int i=1;i<=n;i++){
//        pos[i]=(i-1)/block+1; //pos是第i个元素所在的块
//    }
//
//
//    for(int i=1;i<=t;i++){
//        for(int j=st[i];j<=ed[i];j++){
//            sum[i]+=a[j];  //sum是第i块的区间和
//        }
//    }
//    //end
//
//    int opt,l,r,c;
//    for(int i=1;i<=n;i++){
//        cin>>opt>>l>>r>>c;
//        if(opt==1){
//            cout<>t;
    while (t--) {
        int x,y;
        cin>>x>>y;
        int l=0;
        int r=min(x/2,y/3);
        while (r-l>10) {
            int m1=l+(r-l)/3;
            int m2=r-(r-l)/3;
            if((m1+min((x-m1*2)/4,(y-m1*3)))>
               (m2+min((x-m2*2)/4,(y-m2*3)))){
                r=m2;
            }
            else l=m1;
        }
        int ans=0;
        for(int i=l;i<=r;i++){
            ans=max(ans,i+min((x-i*2)/4,(y-i*3)));
        }
        cout<

装备合成(三分）

C/C++/C#相关栏目本月热门文章