算法基础训练 50 题（三）二分

发表于 更新于 分类于 ，

#JC0301.# Angry Cows

题目描述

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
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，则用求和公式算出未发出的表情数，并用总数减去未发出的表情数，得到已发的表情数：kk-(2k-1-m) (2*k-1-m+1)/2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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值排序，然后再求出前缀和并利用前缀和和求出危险值的最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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吨的火箭，则永远无法使火箭起飞或着陆。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
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

题目描述

利用数学关系硬算即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
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个人满足题目要求。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
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。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
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。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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;
}