目录

二分

二分搜索

查找序列中是否有x

做法（解题思路）：

查找序列中>=x的最小值

解题思路：

性质：

查找序列中>x的最小值

解题思路：

查找序列中<=x的最大值

解题思路：

序列中找最短子序列>=x

​​解题思路：

牛客小白月赛24 B组队

解题思路：

求>x的平方数

解题思路：

求sqrt(x)的精确值

解题思路：

2021年蓝桥杯B组F题

解题思路：

二分

二分搜索

查找序列中是否有x

给定一个有单调性的长度为n的序列，问你里面是否存在某个数x.本质是一种分治的思想

正常暴力循环遍历来做这道题，复杂度是O（n）

用二分搜索，复杂度是O（log n）

做法（解题思路）：

对于有单调性的序列，我们每次检查序列区间中间位置值y，根据y的大小来缩小区域，反复进行此过程直到找到解，或找到可能区域为空为止

递归写法

#include 

using namespace std;
int n;
int fi(int a[], int l, int r)
{
    //如果找到了就返回位置下标记
    if(a[(l+r)/2] == n)
        return (l+r)/2;
    //如果没有找到就压缩左区域或右区域
    if(a[(l+r)/2] > n)
        return fi(a, l, (l+r)/2-1);
    else
        return fi(a, (l+r)/2+1, r);
}

int main()
{
    int a[] = {1, 2, 3, 4, 5, 6, 7 , 8, 9, 10};
    cin >> n;
    cout << fi(a, 0, 9);
    return 0;
}

迭代器写法

#include 

using namespace std;

int main()
{
    int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    int n, l = 0, r = 9, mid;
    cin >> n;
    //循环条件，左端点要小于等于有端点
    while(l <= r)
    {
        //除以2
        mid = (l + r) >> 1;
        if(a[mid] == n)
        {
            cout << "YES";
            return 0;
        }
        //判断大小，移动左右端点
        if(a[mid] > n)r = mid - 1;
        else l = mid + 1;
    }
    if(l > r)cout << "NO";
    return 0;
}

查找序列中>=x的最小值

给定一个有单调性的序列,问你大于等于x的最小值是多少(不存在输出No)

例如:{1,2,4,7,9} , x=4时应该得到4,x=5时应该得到7

解题思路：

 这道题是典型的二分后缀模型，所以直接套入模板，最终结束循环要判断 L 是否越界在进行输出

#include 

using namespace std;

int main()
{
    int a[] = {1, 2, 3, 4, 4, 6, 7, 8, 9};
    int n, l = 0, r = 9, mid;
    cin >> n;
    while(l <= r)
    {
        mid = (l + r) >> 1;
        if(a[mid] == n)
        {
            cout << n;
            return 0;
        }
        if(a[mid] > n)r = mid - 1;
        else l = mid + 1;
    }
    if(l >= 9)
    {
        cout << "NO";
    }
    else
        cout << a[l];
    return 0;
}

性质：

对于前缀模型，右端点 R 结束循环后一定在左区间的最右元素

对于后缀模型，左端点 L 结束循环后一定在右区间的最左元素

查找序列中>x的最小值

给定一个有单调性的序列,问你大于 x 的最小值是多少(不存在输出No)?

例如:{1,2,4,7,9} , x=4时应该得到7,x=5时应该得到7

解题思路：

题目求大于x的最小值，所以是后缀模型，最终输出 L 位置的值

#include 

using namespace std;

int main()
{
    int n, x;
    cin >> n >> x;
    int a[n], l = 0, r = n - 1, mid;
    for(int i = 0; i < n; i++)cin >> a[i];
    while(l <= r) {
        mid = (l + r) >> 1;
        if(a[mid] <= x) {
            l = mid + 1;
        } else{
            r = mid - 1;
        }
    }
    if(l == n) {
        cout << "NO";
    }else {
        cout << a[l];
    }
    return 0;
}

查找序列中<=x的最大值

给定一个有单调性的序列,问你小于等于x的最大值是多少

例如:{1,2,4,7,9} , x=4时应该得到4,x=3时应该得到2

解题思路：

求小于等于 x 的最大值，所以此题为前缀模型，最终输出 R 位置的值

#include 

using namespace std;

int main()
{
    int n, x;
    cin >> n >> x;
    int a[n], l = 0, r = n - 1, mid;
    for(int i = 0; i < n; i++)cin >> a[i];
    while(l <= r) {
        mid = (l + r) >> 1;
        if(a[mid] <= x) {
            l = mid + 1;
        } else{
            r = mid - 1;
        }
    }
    if(r == n) {
        cout << "NO";
    }else {
        cout << a[r];
    }
    return 0;
}

序列中找最短子序列>=x

给定一个正整数序列,让你取一个子段，使得其区间的和大于等于x,问你这个子段最短可能长度是多少。

例如:{1,2,4,7,9} , x=13时应该得到2,x=3时应该得到1

​​解题思路：

根据题目描述可以推出，我们的答案是求最短字段的长度，所以二分答案求的是长度，长度最少为1，最长为字段的总长度，而且当长度越长就越有可能满足>=x，所以此题为后缀模型，先预处理前缀和，在之后通过检查函数来判断是否成立，成立缩减右端点，不成立缩减左端点，在检查函数内，通过滑动窗口来判断这个窗口是否满足>=x，最后输出L即可（因为L会停留在后缀的最左元素）

#include 
using namespace std;
int a[1005], s[1005] = {0}, n, x;

int ok(int mid)
{
    int mx = 0;
    //i为答案的长度
    for(int i = mid; i <= n ; i++)
    {
        //i-mid 与 i 之间构成了长度为 mid 的滑动窗口
        //每次求最大值，原因是最大值是最有可能满足>=x的
        mx = max(mx, s[i] - s[i - mid]);
    }
    //最后传回判断
    return mx >= x;
}

int main()
{
    cin >> n >> x;
    //输入序列，预处理前缀和
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
        s[i] = s[i-1] + a[i];
    }
    int l = 1, r = n, mid;
    while(l <= r)
    {
        mid = (l + r) >> 1;
        //cout << mid << " " << ok(mid) << endl;
        //用检查函数来判断更改哪个端点，如果判断函数传回满足，就缩减右端点
        //如果不满足就缩减左端点， 因为题目是给一个升序的序列，越往后越容易实现题目要求
        if(ok(mid))r = mid - 1;
        else l = mid + 1;
    }
    //此题为后缀模型，越往后越容易实现题目要求
    cout << l;
    return 0;
}

牛客小白月赛24 B组队

题目链接： 牛客小白月赛24 B组队

解题思路：

首先思考题目要我们求最大的人数，这个答案具有单调性的（人数越少越容易满足<=k的条件），所以这题是典型的二分答案前缀模型

首先将所有人的能力存入数组后从小到大进行排序，写一个二分答案前缀模型，然后判断函数内通过滑动窗口来判断是否满足<=k，如果满足就不需要再往后进行判断直接返回 真，否则判断完都没有返回 真，此时就代表不成立，返回 假，因为是前缀模型，最终输出 R

#include
using namespace std;

#define ll long long
const int maxn = 2e5 + 5;
int n, k;
int a[maxn];

bool ok(int mid)
{
    //滑动窗口判断最大值减去最小值是否满足<=k，如果满足了就代表不需要判断后面的了，因为题目只求长度
    for(int i = 1; i + mid - 1 <= n; i++)
    {
        if(a[i + mid - 1] - a[i] <= k)
        {
            return true;
        }
    }
    return false;
}

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        cin >> n >> k;
        for(int i = 1; i <= n; i++)cin >> a[i];
        //将所有人的能力值从小到大排序
        sort(a + 1, a + n + 1);
        int l = 1, r = n;
        //二分答案前缀模型
        while(l <= r)
        {
            int mid = (l + r) >> 1;
            if(ok(mid))l = mid + 1;
            else r = mid - 1;
        }
        cout << r << endl;
    }
    return 0;
}

求>x的平方数 解题思路：

思考此题答案，明显具有单调性，当数字越大越能满足>x的条件，所以此题为二分答案后缀模型，最终输出 L

#include
using namespace std;

#define ll long long
const int maxn = 1e9 + 5;
int x;

int ok(int mid)
{
    if(mid * mid > x)return 1;
    else return 0;
}

int main()
{
    cin >> x;
    int l = 0, r = sqrt(x);
    while(l <= r)
    {
        int mid = (l + r) >> 1;
        if(ok(mid))r = mid - 1;
        else l = mid + 1;
    }
    cout << l;
    return 0;
}

求sqrt(x)的精确值 解题思路：

首先思考此题答案是什么，答案就是x开根号后的值，越大越容易实现x的精确值，所以这是二分答案后缀模型，最终输出L

在不好确定循环次数的时候,不妨可以固定循环的次数T,只$T <= log n 即可

#include
using namespace std;

#define ll long long
const int maxn = 1e9 + 5;
int x;

int main()
{
    cin >> x;
    double l = 0, r = 100;
    while(l <= r)
    {
        double mid = (l + r) / 2.0;
        if(mid * mid < x)l = mid + 1;
        else r = mid - 1;
    }
    cout << l;
    return 0;
}

2021年蓝桥杯B组F题

题目：蓝桥杯2021年第十二届国赛真题-123 - C语言网

解题思路：

根据题目要求我们可以知道

这题主要要会求前N项和的求和公式：（首项+末项）*项数/2

所以解题思路是，我们先将每一行看做一起的，做一个前缀和的预处理，比如2，就代表前两行的和，然后我们可以将一个下标L从1开始到本身的和，拆成他的上一行的前缀和+本行的几个元素的和，所以我们写一个函数sum1（z），去找出他的上一行，再加上它本身的几个元素并返回，由于题目是求字段和，所以我们L的位置的数也要加进来，最终就是sum1(r) - sum1(l - 1)

#include
using namespace std;

#define ll long long
//估算优化了一下开辟前缀和数组的值
const ll maxn = 1e6;
ll sum[maxn];

//js()是首相加末项乘项数除二
ll js(ll i)
{
    return (1 + i) * i / 2;
}

ll sum1(ll z)
{
    //处理L等于1时，L-1为0
    if(z == 0)return 0;
    //估算优化了一下r的值
    ll l = 1, r = 1e6;
    while(l <= r)
    {
        ll mid = (l + r) >> 1;
        if(js(mid) < z)l = mid + 1;
        else r = mid - 1;
    }
    //因为上面循环保证了r是在z所处行的上一行，所以前缀和[R]要加上下一行的几个元素
    //z-r是总下标减去上面前缀和的标
    return sum[r] + js(z - js(r));
}

int main()
{
    ll t, len = 0;
    cin >> t;
    //用len控制元素个数
    for(int i = 1; i <= len; i++)
    {
        //每一次加上一行
        len += i;
        //前缀和处理
        sum[i] = sum[i-1] + js(i);
    }
    while(t--)
    {
        ll l, r;
        cin >> l >> r;
        //L - 1是因为题目求从L-R的字段和
        cout << sum1(r) - sum1(l - 1) << endl;
    }
    return 0;
}