这道题一开始我是想根据用户输入的数字来判断裁判是否正确,结果发现我的思路有漏洞且代码存在超时问题,看了大佬的思路才明白,可以反过来通过裁判的回答得到若干个区间,求被最多区间覆盖的点。设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;
}
本人是初学者,难免会有问题,欢迎大家批评与指正。
京公网安备 11010502036488号