二分查找

手写二分

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
//找到该数的左边界
int left(int x)
{
    int l = 0, r = n - 1, mid = l + r >> 1;
    while(l < r)
    {
        mid = l + r >> 1;
        if(a[mid] < x)  l = mid + 1;
        else r = mid;
    }
    if(a[l] != x) l = -1;
    return l;
}
//找到该数的右边界
int right(int x)
{
    int l = 0, r = n - 1, mid = l + r + 1 >> 1;
    while(l < r)
    {
        mid = l + r + 1 >> 1;
        if(a[mid] > x) r = mid - 1;
        else l = mid;
    }
    if(a[r] != x) r = -1;
    return r;
}

利用STl

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int main()
{
    cin >> n >> q;
    for(int i = 0; i < n; i++) cin >> a[i];
    while(q--)
    {
        int x; cin >> x;
        int p1 = lower_bound(a, a + n, x) - a;
        int p2 = upper_bound(a, a + n, x) - a - 1;
        if(a[p1] != x) p1 = -1;
        if(a[p2] != x) p2 = -1;
        cout << p1 << " " << p2 << '\n';
    }
    return 0;
}

浮点数二分

1
2
3
4
5
6
7
double l = -1e4, r = 1e4, mid;
while(r - l > 1e-8)
{
    mid = (l + r) / 2 ;
    if(a[mid] < n) l = mid;
    else r = mid;
}

应用

最佳牛围栏

  1. 如果用前缀和+暴力的话肯定会超时，那这题用什么算法呢？
  2. 这题的题意可以简化为：选择不少于f个数，让他们的平均值最大。是否可以使用二分，判断是否存在一个平均值大于mid的选择方式，如果存在那么可以在大于mid的范围内继续寻找，如果不存在就在小于mid的范围内寻找，直到找到最后的mid。因为数据范围是\(10^5\)所以使用二分\(nlogn\)不会超时

\(\color{red}{对于二分，二分是二分性而不是单调性 只要满足可以找到一个值一半满足一半不满足即可 而不用满足单调性}\)

  1. 至少f个数这个条件要如何在二分中体现呢？要平均值最大，就需要\(s[i]\)尽可能大，\(s[j-1]\)尽可能小，题目要求的是至少f个，所以可以在\(s[1]\sim s[j - 1]\)范围内寻找最小值min_val，使用s[i]-min_val即可

  2. 要判断mid是否可行，由3可知我们并未记录这段区间有多少数，所以要怎么判断呢？我们可以让每个\(a[i]\)都减去mid这个待判断的平均值，那么最后只需判断那个区间和0的大小即可

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
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
double a[N], s[N];
int n, f;
bool check(double mid)
{
    for(int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i] - mid;
    double min_val = 1e8, ans = -1e8;
    for(int i = f; i <= n; i++)
    {
        min_val = min(min_val, s[i - f]);
        ans = max(ans, s[i] - min_val);
    }
    return ans >= 0; 
}
int main()
{
    cin >> n >> f;
    double l = 0, r = 0, mid;
    for(int i = 1; i <= n; i++) cin >> a[i], r = max(r, a[i]);
    while(r - l > 1e-8)
    {
        mid = (r + l) / 2;
        if(check(mid)) l = mid;
        else r = mid;
    }
    cout << (int)(r * 1000);
    return 0;
}