算法基础训练 50 题(三)二分

#JC0301. Angry Cows

题目描述

利用二分,来查找距离值,通过判断该距离值是否能安排的下所有的牛来调整l和r。

int n,m,a[100005];
int main()
{
    // ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    CI n>>m;
    F(i,1,n)
        CI a[i];
    sort(a+1,a+n+1);

    int l=0,r=a[n]-a[1],mid;
    while (l<=r)
    {
        
        mid=(r+l)/2;
        int x=a[1]+mid,t=2,s=1;
        while (t<=n)
        {
            if(a[t]>=x) x=a[t]+mid,s++;
            t++;
        }
        if (s>=m) l=mid+1;
        else r=mid-1;
    }

    CO l-1 L;
    return 0;
}

#JC0302. Best Cow Fences

题目描述

利用二分,查找平均数,并判断是否存在长度不低于L的子串能达到该平均数平均数。l的初始之为-1e6,r的初始值为1e6。计算出中间值m后,将Ai中的每一个数减去m,大于平均值m的数结果为正,小于平均值m的数结果为负;然后再计算一个前缀和数组d,求最大的平均值,需要找到前缀和d中最少的一个和最大的值,并保证最大的值在最小的值右边,且相距大于L。

int n,ll,a[100005];
double b[100005],d[100005];
int main()
{
    // ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    CI n>>ll;
    F(i,1,n)
        CI a[i];
    
    double l=-1e6,r=1e6,m;
    while (r-l>1e-5)
    {
        m=(l+r)/2;

        F(i,1,n)
            b[i]=a[i]-m;

        F(i,1,n)
            d[i]=b[i]+d[i-1];

        
        double minl=1e10,avg=-1e10;
        F(i,ll,n)
        {
            minl=min(minl,d[i-ll]);
            avg=max(avg,d[i]-minl);
        }

        if (avg>=0) l=m;
        else r=m;
    }

    CO int(r*1000) L;
    return 0;
}

#JC0304. Chat Ban

题目描述

利用二分,找到能发的后一条消息,l和r存储发信息的条数,如果m小于k,则用求和公式m*(m+1)/2算出发送的标签数,如果大于k,则用求和公式算出未发出的表情数,并用总数减去未发出的表情数,得到已发的表情数:k*k-(2*k-1-m)*(2*k-1-m+1)/2

LL t,k,x;
int main()
{
    // ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    CI t;
    while (t--)
    {
        CI k>>x;
        if (k*k<=x)
            CO 2*k-1 L;
        else
        {
            LL l=0,r=2*k-1;
            while (l<r)
            {
                LL m=(l+r)/2;
                LL s=0;
                if (m<=k) s=m*(m+1)/2;
                else s=k*k-(2*k-1-m)*(2*k-1-m+1)/2;
                if (s>=x) r=m;
                else l=m+1;
            }
            CO r L;
        }

    }
    return 0;
}

#JC0305. Cow Acrobats

题目描述

利用贪心,先将数组按照w+s值排序,然后再求出前缀和并利用前缀和和求出危险值的最大值。

struct cow
{
    LL w,s;
} a[50001];
LL n,ans=-0x3f3f3f,s[500001];

bool cmp(cow a,cow b)
{
    return a.w+a.s>b.w+b.s;
}

int main()
{
    // ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    CI n;
    F(i,1,n)
        CI a[i].w>>a[i].s;
    sort(a+1,a+n+1,cmp);
    F(i,1,n)
        s[i]=s[i-1]+a[i].w;
    F(i,1,n)
    {
        LL t=s[n]-s[i];
        t=t-a[i].s;
        ans=max(ans,t);
    }
    CO ans L;
    return 0;
}

#JC0306. Fly

题目描述

最节省的方法便是最后着陆后用完全部的燃料,于是可以倒求出着陆需要的燃料值,不断倒求出燃料值,得到最小的发射燃料量。如果一个燃料只能起飞或着陆1吨的火箭,则永远无法使火箭起飞或着陆。

int n;
double p,ans,m,a[10001],b[10001];
int main()
{
    // ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    CI n>>m;
    int f=1;
    F(i,0,n-1)
    {
        CI a[i];
        if (a[i]==1) f=0;
    }
    F(i,0,n-1)
    {
        CI b[i];
        if (b[i]==1) f=0;
    }

    ans=m;
    if (f)
    {
        FD(i,n-1,0)
        {
            p=ans*1.0/(b[(i+1)%n]-1);
            ans+=p;
            p=ans*1.0/(a[i]-1);
            ans+=p;
        }
        CO fixed << setprecision(6)<< ans-m L;
        // printf("%lf\n",ans-m);
    }
    else 
    {
        CO -1 L;
        // printf("-1\n");
    }
    return 0;
}

#JC0307. Hamburgers

题目描述

利用数学关系硬算即可。

LL n[3],p[3],r,ans,t[3],z[3],am,m;
string s;

LL z3()
{
    m=min(z[0],min(z[1],z[2]));
    ans+=m;
    F(i,0,2)
        n[i]-=m*t[i];
}

LL z2()
{
    m=0x7fffffffffffffff;
    int o;
    F(i,0,2)
        if (z[i]) m=min(m,z[i]);
        else o=i;
    

    if ((t[o]-n[o])*p[o]<=r)
    {
        r-=(t[o]-n[o])*p[o];
        ans++;
        m--;
        F(i,0,2)
            n[i]-=t[i];
        n[o]=0;

        m=min(m,r/(t[o]*p[o]));
        ans+=m;
        r-=m*t[o]*p[o];
        
        F(i,0,2)
            if (z[i]) n[i]-=m*t[i];
    }
}

LL z1()
{
    m=0;
    int o1=0,o2=0,y;
    F(i,0,2)
        if (z[i]) 
        {
            y=i;
            m=z[i];
        }
        else
        {
            if (!o1) o1=i;
            else o2=i;
        }

    if (((t[o1]-n[o1])*p[o1]+(t[o2]-n[o2])*p[o2])<=r)
    {
        r-=((t[o1]-n[o1])*p[o1]+(t[o2]-n[o2])*p[o2]);
        ans++;
        m--;
        n[y]-=t[y];
        n[o1]=0;
        n[o2]=0;

        m=min(m,r/(t[o1]*p[o1]+t[o2]*p[o2]));
        ans+=m;
        r-=m*(t[o1]*p[o1]+t[o2]*p[o2]);

        n[y]-=m*t[y];
    }
}

LL z0()
{
    F(i,0,2)
        am+=p[i]*t[i];

    if (((t[0]-n[0])*p[0]+(t[1]-n[1])*p[1]+(t[2]-n[2])*p[2])<=r)
    {
        r-=((t[0]-n[0])*p[0]+(t[1]-n[1])*p[1]+(t[2]-n[2])*p[2]);
        ans++;
    }
    m=r/am;
    ans+=m;
    r-=m*am;
}

int main()
{
    // ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    CI s;
    CII(n,0,2)
    CII(p,0,2)
    CI r;
    
    F(i,0,s.size()-1)
    {
        if (s[i]=='B') t[0]++;
        if (s[i]=='S') t[1]++;
        if (s[i]=='C') t[2]++;
    }
    
    F(i,1,4)
    {
        int on=0;
        F(i,0,2)
        {
            if (t[i]) z[i]=n[i]/t[i];
            else z[i]=0x7fffffffffffffff;
            if (z[i]) on++;
        }
        if (on==3) z3();
        if (on==2) z2();
        if (on==1) z1();
        if (on==0) z0();
    }
    CO ans L;
    return 0;
}

#JC0308. Keshi Is Throwing a Party

题目描述

利用二分,判断是否能找到中间值m个人满足题目要求。

int t;
int n,a[200005],b[200005];
int check(int m)
{
    int c=0;
    F(i,1,n)
        if (m-c-1<=a[i]&&c<=b[i]) c++;
    return c>=m;
}

int main()
{
    // ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    CI t;
    while (t--)
    {
        CI n;
        F(i,1,n)
            CI a[i]>>b[i];
        
        int l=0,r=n+1;
        while (l<=r)
        {
            int m=(l+r)/2;
            if (check(m)) l=m+1;
            else r=m-1;
        }
        CO r L;
    }
    return 0;
}

#JC0309. Monthly Expense

题目描述

利用二分,查找合适的花费值,l的初始值为每天花费的最小值,r的初始值为总花费。判断是否能分出M组。

int n,m,a[100005];
int check(int mid)
{
    int x=1,t=0;
    F(i,1,n)
    {
        if (t+a[i]<=mid) t+=a[i];
        else
        {
            t=a[i];
            x++;
        }
    }
    return x<=m;
}
int main()
{
    // ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    CI n>>m;
    int l=0,r=0;
    F(i,1,n)
    {
        CI a[i];
        l=max(l,a[i]);
        r+=a[i];
    }
    while (l<=r)
    {
        int mid=(l+r)/2;
        
        if (check(mid)) r=mid-1;
        else l=mid+1;
    }    
    CO l L;
    return 0;
}

#JC0310. New Year’s Problem

题目描述

利用二分,l和r寻找joy值,然后将矩阵中的每一个joy值减去中间值m,并判断每一列是否都有一个值大于m,任意有一行有两个值大于m。

int t,n,m;
int main()
{
    // ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    CI t;
    while (t--)
    {
        CI m>>n;
        int a[m+1][n+1];

        int l=0x3f3f3f,r=0;
        F(i,1,m)
            F(j,1,n)   
            {     
                CI a[i][j];
                l=min(l,a[i][j]);
                r=max(r,a[i][j]);
            }
        
        while (l<=r)
        {
            int mid=(l+r)/2;

            int b[m+1][n+1],fm[m+1]={0},fn[n+1]={0},f2=1,f3=0;
            F(i,1,m)
            {
                F(j,1,n)
                    if (a[i][j]>=mid)
                    {
                        fm[i]++;
                        fn[j]++;
                    }

                if (fm[i]>=2) f3=1;
            }

            F(j,1,n)
                if (!fn[j]) f2=0;

            if (f2&&f3) l=mid+1;
            else r=mid-1;
        }
        CO r L;
    }
    return 0;
}

#JC0311. Poisoned Dagger

题目描述

利用二分,查找k值,并判断k值伤害是否能达到h。

LL t,n,h,a[101];

int check(LL m)
{
    LL s=m;
    F(i,2,n)
        s+=min(m,a[i]-a[i-1]);
    return s>=h;
}

int main()
{
    // ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    CI t;
    while (t--)
    {
        CI n>>h;
        CII(a,1,n);
        LL l=1,r=h;
        while (l<=r)
        {
            LL m=(l+r)/2;
            if (check(m)) r=m-1;
            else l=m+1;
        }

        CO l L;
    }
    return 0;
}
知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇