题目：二分

来源：牛客网

题意

你猜一个数，裁判回答你这个数是大了还是小了还是猜对了。但是裁判都傻得很，不知道自己说的对没对，让你求裁判最多有多少个回答是正确的。

简而言之就是裁判在瞎说大小，让你求裁判最多说对了几次。

看到题目是二分你可不要被二分给迷惑了，我反正想了半天也没想出来用怎么用二分写这个题。我来说一下我的思路：

首先你说了一个数a，总共有三种情况：

1. 裁判说数大了，那么裁判说对的取值范围是(-∞,a]
2. 裁判说数小了，那么裁判说对的取值范围是[a,+∞)
3. 裁判说数一样，那么裁判说对的取值范围是[a,a]

那么我们只需要求最大有多少个区间重叠了就行，类似于第一节课讲解的种树一题。同学们仔细去复习一遍吧。

解法

差分、离散化都行，下面给出我的代码，就是把种树的代码改了一点点而已：

#include <bits/stdc++.h>

using namespace std;
#define foru(i, a, b) for(auto i=(a);i<(b);++i)
#define ford(i, a, b) for(auto i=(a);i>(b);--i)
#define maxn 100005
typedef long long ll;

inline int read() {
    char ch = getchar();
    int f = 1, x = 0;
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
        x = (x << 1) + (x << 3) + ch - '0', ch = getchar();
    return f * x;
}

struct position{
    int value;
    bool is_left;
    bool operator < (const position& p){
        if(value == p.value) // 若两个数一样大，则左端点在前
            return is_left > p.is_left;
        return value < p.value;
    }
}pos[maxn << 1];

int main() {
    int n = read(), num, c;
    foru(i,0,n) {
        scanf("%d %c", &num, &c);
        if (c == '.') {
            pos[i << 1].value = num;
            pos[(i << 1) + 1].value = num;
        } else if (c == '+') {
            pos[i << 1].value = INT_MIN;
            pos[(i << 1) + 1].value = num - 1;
        } else {
            pos[i << 1].value = num + 1;
            pos[(i << 1) + 1].value = INT_MAX;
        }
        pos[i << 1].is_left = true; //左端点
        pos[(i << 1) + 1].is_left = false; //右端点
    }
    sort(pos,pos + (n << 1)); //把区间端点从小到大排序
    int cover = 0, ans = 0; //cover表示区间重叠的数量
    foru(i,0,n << 1){
        if(pos[i].is_left)
            cover++;
        else
            cover--;
        ans = max(ans, cover);
    }
    cout << ans;
    return 0;
}