大一寒假训练六（二分查找）（未完待续……）2020.1.5

今天的二分真的是有点玄学！！！但是兴安家族个陈宇老师提前拜了个早年，QAQ！Happy！！今天练习结束时间提前了，所以榜单有点难看~

Problem:A    二分查找

核心思路：题干中说按有序排列，直接暴力就ok。

#include <bits/stdc++.h>
using namespace std;

int y;
int main()
{
    ios::sync_with_stdio(0);
    int n, x;
    while (cin >> n >> x)
    {
        int ans = 0;
        for (int i = 1; i <= n; i++)
        {
            cin >> y;
            if (x < y && !ans)
            {
                ans = i;
            }
        }
        cout << ans - 1 << endl;
    }
    return 0;
}

Problem:B    小清新的二分查找之旅

核心思路：十分基础的二分查找，注意审题。

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
const int M = 1e6;
LL a[M], b[M];

int main()
{
    //ios::sync_with_stdio(0);
    int n, q;
    while (~scanf("%d%d", &n, &q))
    {
        for (int i = 1; i <= n; i++)
            scanf("%lld", &a[i]);
        for (int i = 1; i <= q; i++)
            scanf("%lld", &b[i]);
        sort(a + 1, a + 1 + n);
        LL maxx = a[n];
        for (int i = 1; i <= q; i++)
        {
            int flag = 0;
            if (maxx < b[i])
                flag = 0;
            else
            {
                int head = 1, foot = n, mid = head + (foot - head) / 2;//防爆（再此题中没有用，可以养成习惯）
                while (head <= foot)    //手写二分
                {
                    if (a[mid] == b[i])
                    {
                        flag = 1;
                        break;
                    }
                    if (a[mid] < b[i]) //小的时候
                        head = mid + 1;
                    else               //大的时候
                        foot = mid - 1;
                    mid = head + (foot - head) / 2;
                }
            }
            if (flag)
                printf("no\n");
            else
                printf("YES\n");
        }
    }
}

Problem:C    小清新的函数坐标-二分

核心思路：实数型的二分，注意跳出的时间。

#include <bits/stdc++.h>
using namespace std;

double f(double x)      //定义函数
{
    return 0.0001 * pow(x, 5) + 0.003 * pow(x, 3) + 0.5 * x - 3;
}
int main()
{
    double y;
    while (~scanf("%lf", &y))
    {
        double head = -1 * 20, foot = 20, mid = (foot + head) / 2;
        while (f(foot) - f(head) >= 1e-6)//确定合适的跳出范围，由于本博主水平有限，只能看脸了。
        {
            if (f(mid) > y) //大的时候
                foot = mid;
            else            //小的时候
                head = mid;
            mid = (foot + head) / 2;
        }
        printf("%.4lf\n", mid);
    }
    return 0;
}

Problem:D    小清新的二倍问题加强版-二分-桶排（NEFU 1647）

核心思路：可以用二分，也可以用桶排序。

方法一：桶排，制作计数器，记录数的有无。

#include <bits/stdc++.h>

using namespace std;
const int M = 1e5 + 5;
int num[M], flag[200010];
int main()
{
    ios::sync_with_stdio(0);
    int t;
    cin >> t;
    while (t--)
    {

        int tmp = 1;
        int x;
        long long ans = 0;
        memset(flag, 0, sizeof(flag));
        while (cin >> x)
        {
            if (x == 0)
                break;
            else
            {
                num[tmp] = x;
                flag[x] = 1;        //计数器    
                tmp++;
            }
        }
        tmp--;
        for (int i = 1; i <= tmp; i++)
        {
            if (flag[2 * num[i]])   //判断是否存在
                ans++;
        }
        cout << ans << endl;
    }
    return 0;
}

方法二：二分查找。

核心思路：利用upper_bound函数，直接返回坐标，再进行判断。

#include <bits/stdc++.h>

using namespace std;
const int M = 1e4 + 5;
int num[M];
int main()
{
    ios::sync_with_stdio(0);
    int n;
    cin >> n;
    while (n--)
    {
        int tmp1, ans = 0, x, tmp = 0;
        while (cin >> x && x)
            num[++tmp] = x;
        sort(num + 1, num + 1 + tmp);
        for (int i = 1; i <= tmp; i++)
        {
            tmp1 = upper_bound(num + 1, num + 1 + tmp, 2 * num[i]) - num - 1;//upper_bound函数返回第一个大于他的数坐标
            if (2 * num[i] == num[tmp1] || 2 * num[i] == num[tmp1 + 1])      //判断tmp1是否符合题干条件
                ans++;
        }
        cout << ans << endl;
    }

    return 0;
}

Problem:E    简单几何-二分（NEFU 1303）

#include <bits/stdc++.h>

using namespace std;
double h;
const double pi = acos(-1.0); //得到3.14.......
double judge(double r)        //定义函数
{
    if (pow(r, pi) >= h * (pi * r * r - r))
        return 1;
    else
        return 0;
}

int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        double head = 0, foot = 1e5, mid;
        scanf("%lf", &h);
        while (foot > head)
        {
            mid = (head + foot) / 2.0;
            if (foot - head <= 1e-8) //这个是他玄学的地方，我也不知到为啥QAQ
                break;
            if (judge(mid)) //数值大，区分与整数型二分的赋值
                foot = mid;
            else //数值小
                head = mid;
        }
        printf("%.4lf\n", mid);
    }
    return 0;
}