First Year Winter Holiday Training 2020.1.5 //Binary Search

First Year Winter Holiday Training 2020.1.5

dichotomy

First, the most basic binary search in the dichotomy.
A very magical algorithm/idea:
Two points, the score is the answer, directly in the answer in the range of two points, a value to determine whether the answer is the answer, and transfer
If we know the range of candidate answers (min,max) (monotonically ordered), sometimes we don't have to calculate the answer, just apply the "dichotomy" process within this range and get closer to the answer (finally, get the answer)!
Skip unnecessary comparisons and choices by a large margin with the dichotomy method

In C++, there are two functions that directly find subscripts greater than or equal to the number to be found.
Usage of upper_bound() and lower_bound()
Are binary functions, the header file "algorithm" can also use "bits/stdc++.h"
upper_bound returns the subscript of the first greater element;
lower_bound returns the first subscript greater than or equal to the element;
int point[10] = {1,3,7,7,9};
int tmp = upper_bound(point, point + 5, 7) - point; //from smallest to largest, where can 7 insert the array point at most
printf("%d\n",tmp);
tmp = lower_bound(point, point + 5, 7) - point; /// from small to large, 7 inserts at least where in the array point
printf("%d\n",tmp);
Binary Search
Use the function line just mentioned to solve the problem.

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int x,n;
    while(cin>>n>>x)
    {
        int a[1000005];
        for(int i=0;i<n;i++)
        {
            cin>>a[i];
        }
        int ans;
        ans=upper_bound(a,a+n,x)-a;
        cout<<ans<<endl;
    }
    return 0;
}

A fresh journey to dichotomy

Looks like it's still not difficult, watch the topic, find the return NO, not the return YES

#include <bits/stdc++.h>
using namespace std;
int n, q;
int a[1000005];
int erfen(int a[], int left, int right, int x)
{
    int mid;
    while (left < right)
    {
        mid = (left + right) / 2;
        if (a[mid] == x)
        {
            return mid;
        }
        else if (a[mid] < x)
        {
            left = mid + 1;
        }
        else
        {
            right = mid;
        }
    }
    return 0;
}
int main()
{
    while (scanf("%d%d", &n, &q) != EOF)
    {
        int t;
        for (int i = 0; i < n; i++)
        {
            scanf("%d", &a[i]);
        }
        for (int i = 0; i < q; i++)
        {
            scanf("%d", &t);
            if (t < a[0] || t > a[n - 1])
            {
                printf("YES\n");
            }
            else if (erfen(a, 0, n - 1, t))
            {
                printf("no\n");
            }
            else
            {
                printf("YES\n");
            }
        }
    }
}

Clear Function Coordinates-Bisection

Coordinates are real numbers. Note the input and output formats, as well as the two-part conditional notation.

#include <bits/stdc++.h>
using namespace std;
double f(double x)
{
    return 0.0001 * x * x * x * x * x + 0.003 * x * x * x + 0.5 * x - 3;
}
double find1(double l, double r, double y)
{
    double mid = (l + r) / 2;
    while (r - l >= 1e-6)
    {
        if (f(mid) > y)
        {
            r = mid;
        }
        else
        {
            l = mid;
        }
        mid = (l + r) / 2;
    }
    return mid;
}
int main()
{
    double y;
    double p;
    while (scanf("%lf", &y) != EOF)
    {
        p = find1(-20, 20, y);
        printf("%.4f\n", p);
    }
    return 0;
}

Small Fresh Double Problem Enhanced Edition-Divide-Barrel Row

What can I do with barrel drainage?

#include <bits/stdc++.h>
using namespace std;
int tong[100005];
int main()
{
    int n;
    cin>>n;
    while (n--)
    {
        memset(tong, 0, sizeof(tong));

        int ans = 0;
        int t;
        scanf("%d", &t);
        while (t)
        {
            tong[t]++;
            scanf("%d", &t);
        }
        for (int i = 1; i <= 50000; i++)
        {
            if (tong[i] != 0 && tong[2 * i] != 0)
            {
                ans++;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

Simple Geometry-Binary

Represent both volumes and divide them in a given interval to find the desired value.

#include <bits/stdc++.h>
using namespace std;
const double PI = acos(-1.0);
double yz(double r, int h)
{
    return PI * r * r * h;
}
double v1(double r, int h)
{
    return r * h;
}
int h;
double find2(double l, double r, double h)
{
    double mid = (l + r) / 2.0;
    while (r - l > 1e-8)
    {
        if (yz(mid, h) - v1(mid, h) <= pow(mid, PI))
        {
            r = mid;
        }
        else
        {
            l = mid;
        }
        mid = (l + r) / 2.0;
    }
    return mid;
}
double a[1000005];
int main()
{
    int t;
    memset(a, 0, sizeof(a));
    for (int i = 1; i <= 100000; i++)
    {
        a[i] = find2(0, 100000, i);
    }
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d", &h);
        printf("%.4f\n", a[h]);
    }
    return 0;
}

Dichotomy for Maximum-Minimum, Minimum-Maximum

The big game is coming. This is one of the most difficult problems for Arctium to solve. Fortunately, there are some rules to follow.
(Although I can't read it)

Small Fresh Cut Cord - Divide

//Bipartite check() function summary: Some values meet the criteria, that is, when the maximum value is evaluated, the check() function >=k returns 1,
//The corresponding answer is also recorded when check() returns 1!
//When some values meet the criteria, that is, when the minimum value is found, the check() function > k returns 1.
//The corresponding answer is in the position of = sign, that is, when check() returns 0, record it!
#include <bits/stdc++.h>
using namespace std;
int n, k;
int a[10005];
int check(int x)
{
    int num = 0;
    for (int i = 0; i < n; i++)
    {
        num += a[i] / x;
    }
    if (num >= k)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
int main()
{
    while (scanf("%d %d", &n, &k) != EOF)
    {
        int mx = -99999999;
        for (int i = 0; i < n; i++)
        {
            scanf("%d", &a[i]);
            if (mx < a[i])
            {
                mx = a[i];
            }
        }
        int mid = 0;
        int ans = 0;
        int l, r;
        l = 0;
        r = mx;
        while (l <= r)      //Must have equal to;
        {
            mid = (l + r) / 2;
            if (check(mid) == 1)
            {
                ans = mid;
                l = mid + 1;
            }
            else
            {
                r = mid - 1;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

Antique Selling-DP-Divide

The minimum value in the previous question is the largest, which means the maximum value is the smallest.Then I'll come.Follow the notes on the previous topic.Get a check function on OK

#include <bits/stdc++.h>
using namespace std;
int a[100005];
int n, m;
int check(int mid)
{
    int num = 0;
    int tmp = 0, s = 0;
    for (int i = 1; i <= n; i++)
    {
        tmp = 0;
        s = s + a[i];
        if (s > mid)
        {
            s = a[i];
            tmp = 1;
            num++;
        }
    }
    if (tmp == 0)
        num++;
    if (num > m)
        return 1;
    else
        return 0;
}
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        scanf("%d%d", &n, &m);
        memset(a, 0, sizeof(a));
        int mx = -999999;
        int sum=0;
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", &a[i]);
            if (mx < a[i])
            {
                mx = a[i];
            }
            sum+=a[i];
        }
        int l, r;
        r = sum;
        l = mx;
        int ans = 0;int mid = 0;
        while (l <= r)
        {
            mid = (l + r) / 2;
            if (check(mid) == 1)
            {
                l = mid + 1;
            }
            else
            {
                ans = mid;
                r = mid - 1;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

Real Cord Cutting Edition-Divide

Nothing special to note, just look at the small set of real number processing

#include <bits/stdc++.h>
//Real number carry problem, turn to integer first;
using namespace std;
int a[100005];
int n, k;
double t;
int check(int mid)
{
    long long num = 0;
    for (int i = 1; i <= n; i++)
    {
        num += (int)(a[i] / mid);
    }
    if (num >= k)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
int main()
{
    while (scanf("%d%d", &n, &k) != EOF)
    {
        double mx = -999999;
        for (int i = 1; i <= n; i++)
        {
            scanf("%lf", &t);
            a[i] = (int)(t * 100);
            if (mx < a[i])
            {
                mx = a[i];
            }
        }
        int mid = 0;
        int l, r, ans = 0;
        r = mx;
        l = 0;
        while (l <= r)
        {
            mid = (l + r) / 2.0;
            if (mid == 0)
                break;
            if (check(mid) == 1)
            {
                ans = mid;
                l = mid + 1;
            }
            else
            {
                r = mid - 1;
            }
        }
        printf("%.2f", ans / 100.00);
    }
    return 0;
}

Segmentation-Bisection

The difficulty is still the way to write the check function. Just follow the method mentioned before and practice more. After all, they all survived.

#include <bits/stdc++.h>
using namespace std;
int a[100005];
int m, n;
int check(int mid)
{
    int num = 0;
    int tmp = 0, s = 0;
    for (int i = 1; i <= n; i++)
    {
        tmp = 0;
        s = s + a[i];
        if (s > mid)
        {
            s = a[i];
            tmp = 1;
            num++;
        }
    }
    if (tmp == 0)
        num++;
    if (num > m)
        return 1;
    else
        return 0;
}
int main()
{
    while (scanf("%d%d", &n, &m) != EOF)
    {
        int mx = -9999;
        int sum = 0;
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", &a[i]);
            if (mx < a[i])
            {
                mx = a[i];
            }
            sum += a[i];
        }
        int mid = 0;
        int ans = 0;
        int l = mx, r = sum;
        while (l <= r)
        {
            mid = (l + r) / 2;
            if (check(mid) == 1)
            {
                l = mid + 1;
            }
            else
            {
                ans = mid;
                r = mid - 1;
            }
        }
        printf("%d\n", ans);
    }
}

Binary Search Enhanced Edition

The so-called enhanced version is also known as multiple sorting, and sorts are available

#include<bits/stdc++.h>
using namespace std;
int a[2000010];
int main()
{
    int x,n;
    while(cin>>n>>x)
    {
        memset(a,0,sizeof(a));
        for(int i=0;i<n;i++)
        {
            cin>>a[i];
        }
        sort(a,a+n);
        int ans;
        ans=upper_bound(a,a+n,x)-a;
        cout<<ans<<endl;
    }
    return 0;
}

After a long time, it is really the problem of these days is too nauseous, so a good digestion will make a different impression.

Seven original articles were published, 0 won and 1279 visited
Private letter follow

Posted on Sat, 11 Jan 2020 17:09:39 -0800 by cheesehead