祎隋

郁闷的小G
Description有5种类型的题E,EM,M,MH,H若干,其中E,EM可用来出第一题,EM,M,MH可用来出...
扫描右侧二维码阅读全文
15
2019/02

郁闷的小G

Description

有5种类型的题E,EM,M,MH,H若干,其中E,EM可用来出第一题,EM,M,MH可用来出第二题,MH,H可用来出第三题,求最多可出多少场模拟赛。(设N为最大数,$1≤N≤10^18$)

Solution

我干考试时懵了直接上了个大模拟,结果用二分简单到爆炸!!!

模拟:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll e,em,m,mh,h,a,b,c,x=1,y=1;
int main(){
     scanf("%lld%lld%lld%lld%lld",&e,&em,&m,&mh,&h);
     a=e+em,b=m,c=mh+h;
     if(a<=b) x=0;
     if(c<=b) y=0;
     if(!x&&!y){
         ll ans=min(a,min(b,c));
         printf("%lld",ans);
     }
     else if(!x){
         ll mid=(b+c)/2;
         if(mid-b<=mh) y=mid-b;
         else y=mh;
         ll minn=y+b;
         ll ans=min(a,minn);
         printf("%lld",ans);
     }
     else if(!y){
         ll mid=(a+b)/2;
         if(mid-b<=em) x=mid-b;
         else x=em;
         ll minn=b+x;
         ll ans=min(minn,c);
         printf("%lld",ans);
     }
     else{
         if(a>c){
             ll mv=a-c;
             if(mv>em) mv=em;
            a=a-mv; 
             if(b+mv>=c){
                 printf("%lld",c);
            }
            else{
                if(mv==em){
                    b+=mv;
                    ll mid=(b+c)/2;
                     if(mid-b<=mh) y=mid-b;
                     else y=mh;
                     ll minn=y+b;
                     printf("%lld",minn);
                }
                else{
                    b+=mv;
                    em-=mv;//还剩的步数 
                    ll mvv=min(em,mh);
                    ll cnt=(c-b)/3;
                    if(cnt>mvv) cnt=mvv;
                    ll minn=b+cnt*2;
                    c=c-cnt,a=a-cnt;em-=mvv;mh-=mvv;
                    if(minn<c){
                       if(em){
                           ll mid=(minn+c)/2;
                         if(mid-minn<=em) y=mid-minn;
                         else y=em;
                         minn=minn+y;
                       }
                       if(mh){
                           ll mid=(minn+c)/2;
                         if(mid-minn<=mh) y=mid-minn;
                         else y=mh;
                         minn=minn+y;
                       }    
                    }
                    printf("%lld",minn);
                }
            }
         }
         else{
             ll mv=c-a;
             if(mv>mh) mv=mh;
            c=c-mv; 
             if(b+mv>=a){
                 printf("%lld",a);
            }
            else{
                if(mv==mh){
                    b+=mv;
                    ll mid=(a+b)/2;
                     if(mid-b<=em) x=mid-b;
                     else x=em;
                     ll minn=b+x;
                     printf("%lld",minn);
                }
                else{
                    b+=mv;
                    mh-=mv;//还剩的步数 
                    ll mvv=min(em,mh);
                    ll cnt=(c-b)/3;
                    if(cnt>mvv) cnt=mvv;
                    ll minn=b+cnt*2;
                    c=c-cnt,a=a-cnt;em-=mvv;mh-=mvv;
                    if(minn<c){
                       if(em){
                           ll mid=(minn+c)/2;
                         if(mid-minn<=em) y=mid-minn;
                         else y=em;
                         minn=minn+y;
                       }
                       if(mh){
                           ll mid=(minn+c)/2;
                         if(mid-minn<=mh) y=mid-minn;
                         else y=mh;
                         minn=minn+y;
                       }    
                    }
                    printf("%lld",minn);
                }
            }
             
         }
     }
    
    return 0;
}

滔滔的二分:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
bool check(LL mid,LL A,LL B,LL C,LL A_B,LL B_C){
    if(A<mid){if(A+A_B<mid)return false;A_B-=mid-A;}B+=A_B;
    if(B<mid){if(B+B_C<mid)return false;B_C-=mid-B;}
    C+=B_C;if(C<mid)return false;
    return true;
}
int main(){
    LL A,B,C,A_B,B_C;
    scanf("%lld%lld%lld%lld%lld",&A,&A_B,&B,&B_C,&C);
    LL L=min({A,B,C}),R=max({A+A_B,B+A_B+B_C,B_C+C}),ans;
    while(L<=R){
        LL mid=(L+R)>>1;
        if(check(mid,A,B,C,A_B,B_C))ans=mid,L=mid+1;
        else R=mid-1;
    }
    printf("%lld",ans);
    return 0;
}
Last modification:February 15th, 2019 at 09:56 pm

Leave a Comment