牛客算法入门课练习赛1
链接：https://ac.nowcoder.com/acm/contest/5773/D
题目描述
我们刚刚学了二分查找——所谓二分查找就是在一堆有序数里找某个符合要求的数。在学完二分查找之后如果让你玩猜数游戏（裁判选定一个目标数字，你说一个数裁判告诉你是高了还是低了直到你猜到那个数）的话，显然你会用二分的方式去猜。 但是不是每一个玩猜数游戏的人都知道二分是最好，甚至一个健忘的玩家都有可能在得到裁判回答的下一个瞬间就忘了他之前问了什么以及裁判的回答），而现在更可怕的是，这个告诉你猜的数是高还是低的裁判他也很健忘，他总是薛定谔的记得这个目标数字，也就是说他的回答有可能出错。我们已经不关心这个不靠谱的游戏本身了，我们更关心裁判这个薛定谔的记得到底有几个是记得...... 现在给出这个健忘的玩家的所有猜测和裁判的所有回答，问裁判最多能有多少次是记得目标数字的，即裁判的回复是符合情况的。
输入描述:
第一行包含一个正整数n，表示裁判的回答数（也是玩家的猜数次数）。接下来n行，首先是猜的数，然后是一个空格，然后是一个符号。符号如果是“+”说明猜的数比答案大，“-”说明比答案小，“.”说明猜到了答案。
输出描述:
包含一个正整数，为裁判最多有多少个回答是正确的。
题目给了数值的最大范围时不超过int的最大值，用inx保存最大值，假设猜的一个数是x，当这个数猜大了时，那么答案就在[-inx,x - 1]中，如果猜小了的话，答案就在[x + 1,inx]中，相等答案就是[x],当并不知道裁判的那些回答是正确的，
#include <bits/stdc++.h>
#include <iostream>
#define Maxsize 1000005
#define LL long long
const int inx = INT_MAX;
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
// srand(time(NULL));
// m = rand() % 1000 + 1;
//交换元素
map<int,int>a;
int main()
{
int n,i,b;
char x;
cin >> n;
for(i = 1; i <= n; i++){
cin >> b >> x;
if(x == '+'){
a[-inx]++,a[b]--;
}
else if(x == '-'){
a[b + 1]++,a[inx]--;
}
else{
a[b]++,a[b + 1]--;
}
}
int sum = 0,Max = -1;
map<int,int> :: iterator it;
for(it = a.begin(); it != a.end(); it++){
sum += it -> second;
it -> second = sum;
if(Max < it -> second) Max = it -> second;
}
cout << Max;
return 0;
} 
