题解 | #二分#

二分 (nowcoder.com)

问题描述：根据对话，找可能的最多正确的对话。

思路：

​ 如果是 val +，说明猜的数val比答案要大，此时，答案在区间(-inf, val)。

​ 如果是val -，说明猜的数val比答案要小，此时，答案在区间(val, inf)。

​ 如果是val .，说明猜的数val等于答案，此时，答案在区间[val, val + 1)。

​ 可以用差分求最大覆盖区间。数据离散，可以用map代替差分离散化。

代码：

void solve() {
    LL inf = LONG_LONG_MAX - 123456789;
    int n; cin>>n;
    map<LL,LL> mll;
    char op[2];
    rep(i,1,n) {
        int v; cin>>v>>op;
        if(op[0] == '.') { // 等于 [val, val + 1)
            mll[v]++, mll[v+1]--;
        }
        else if(op[0] == '+') { // 大 (-inf, v)
            mll[-inf]++;
            mll[v]--; 
        } else { // 小 (v+1, inf)
            mll[v+1]++;
            mll[inf]--;
        }
    }
    int ans = 0, sum = 0;
    for(auto t: mll) {
        sum += t.vs;
        ans = max(sum, ans);
    }
    cout<<ans;
}