这道题一开始我是想根据用户输入的数字来判断裁判是否正确,结果发现我的思路有漏洞且代码存在超时问题,看了大佬的思路才明白,可以反过来通过裁判的回答得到若干个区间,求被最多区间覆盖的点。设inf为最大整数,玩家输入的值为a;当裁判回答‘.’时,说明a可能正确,即答案可能在区间【a,a+1)。当裁判回答‘.+时,说明a可能大于正确答案,即答案可能在区间(-inf,a)。当裁判回答‘-’时,说明可能小于正确答案,即答案可能在区间【a+1,inf)。
map储存的是差分数组的关键节点
当然运用代码实现的时候,需要用到差分思想,对某区间的数都加1,可以变为在端点处操作。
#include<bits/stdc++.h>
#include<vector>
using namespace std;
const int inf=INT_MAX;//定义最大值,#include<bits/stdc++.h>包含该头文件
map<int,int> M;
vector<int> v1(100000);
vector<char> v2(100000);
int main(){
    int n=0;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>v1[i]>>v2[i];
        if(v2[i]=='.') {
            M[v1[i]]++;
            M[v1[i]+1]--;
        }
        else if(v2[i]=='+'){
            M[-inf]++;
            M[v1[i]]--;
        }
        else{
            M[v1[i]+1]++;
            M[inf]--;
        }
    }
    int ans=-inf;
    int sum=0;  
    for(auto a:M){
        sum+=a.second;//求前缀和得到每个数包含在区间的次数
        if(sum>ans) ans=sum;//求最大次数
    }
    cout<<ans;
}
本人是初学者,难免会有问题,欢迎大家批评与指正。