首页 algorithm 杂杂的算法知识

# 二分查找

手写二分

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。因为数据范围是10510^5 所以使用二分nlognnlogn 不会超时

\color{red}

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

  2. 要判断 mid 是否可行，由 3 可知我们并未记录这段区间有多少数，所以要怎么判断呢？我们可以让每个a[i]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;
}