一些有用的c++函数

发表于 更新于 分类于 阅读次数： 阅读次数： 本文字数： 328 阅读时长 ≈ 1 分钟

二分答案

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
/// @brief 二分答案（闭区间）
/// @tparam T 数字类型
/// @param l 左初始值
/// @param r 右初始值
/// @param check 检查答案在左还是右的函数，若true则向右移动，否则向左移动
/// @param reverseAns 是否反转答案
/// @return 答案
template <typename T = int>
T ba(T l, T r, bool (*check)(T), bool reverseAns = false)
{
    T m = 0, ans = 0;
    while (r >= l)
    {
        m = (l + r) >> 1;

        // cout<<"l: "<<l<<" r: "<<r<<" m: "<<m<<endl;

        if (check(m))
        {
            ans = reverseAns ? ans : m;
            l = m + 1;
        }
        else
        {
            ans = reverseAns ? m : ans;
            r = m - 1;
        }
    }

    return ans;
}

/// @brief 二分答案（左开右闭，向左寻找）
/// @tparam T 数字类型
/// @param l 左初始值
/// @param r 右初始值
/// @param check 检查答案在左还是右的函数，若true则向右移动，否则向左移动
/// @return 答案
template <typename T = int>
T baL(T l, T r, bool (*check)(T))
{
    while (l < r)
    {
        T m = (l + r) >> 1;

        // cout<<"l: "<<l<<" r: "<<r<<" m: "<<m<<endl;

        if (check(m))
            l = m + 1;
        else
            r = m;
    }

    return r;
}

/// @brief 二分答案（左闭右开，向右寻找）
/// @tparam T 数字类型
/// @param l 左初始值
/// @param r 右初始值
/// @param check 检查答案在左还是右的函数，若true则向右移动，否则向左移动
/// @return 答案
template <typename T = int>
T baR(T l, T r, bool (*check)(T))
{
    while (l < r)
    {
        T m = (l + r + 1) >> 1;

        // cout<<"l: "<<l<<" r: "<<r<<" m: "<<m<<endl;

        if (check(m))
            l = m;
        else
            r = m - 1;
    }

    return r;
}