c++算法基础必刷题目——前缀和与差分-创新互联

NC207053 二分

题目描述
  我们刚刚学了二分查找——所谓二分查找就是在一堆有序数里找某个符合要求的数。在学完二分查找之后如果让你玩猜数游戏（裁判选定一个目标数字，你说一个数裁判告诉你是高了还是低了直到你猜到那个数）的话，显然你会用二分的方式去猜。

  但是不是每一个玩猜数游戏的人都知道二分是最好，甚至一个健忘的玩家都有可能在得到裁判回答的下一个瞬间就忘了他之前问了什么以及裁判的回答），而现在更可怕的是，这个告诉你猜的数是高还是低的裁判他也很健忘，他总是薛定谔的记得这个目标数字，也就是说他的回答有可能出错。我们已经不关心这个不靠谱的游戏本身了，我们更关心裁判这个薛定谔的记得到底有几个是记得…
现在给出这个健忘的玩家的所有猜测和裁判的所有回答，问裁判最多能有多少次是记得目标数字的，即裁判的回复是符合情况的。

输入描述:
第一行包含一个正整数n，表示裁判的回答数（也是玩家的猜数次数）。
接下来n行，首先是猜的数，然后是一个空格，然后是一个符号。符号如果是“+”说明猜的数比答案大，“-”说明比答案小，“.”说明猜到了答案。

输出描述:
包含一个正整数，为裁判最多有多少个回答是正确的。

示例1
输入
4
5 .
8 +
5 .
8 -

输出
3

说明
当目标数组是5时，5 . 5 . 8 + 这三个回答都是正确的

备注:
n≤100000
所有数的大小都小于int类型大值。

解题思路：
1、如果是x +，那么当正确的数m>x时该式子成立，如果是x .，那么当正确的数m=x时该式子成立，如果是x -，那么当正确的数m=x时该式子成立

2、题目要求的是尽可能多的式子成立，那么我们可以枚举出现过的数字，最优解一定在里面的，下面解释样例

3、样例只出现了5，8，那么我们只要判断这两个数字是正确的数字的时候的值，当正确的数为5时，3个式子成立，当正确的数为8时，1个式子成立，这里不太符合，但是保底最小成立数是1

4、如果直接用数组去做前缀和，那么空间复杂度是int的大值，时间复杂度也是，显然是不理想的。需要用一个map去离散化数据，比如用ma[0]代表5，用a[1]代表8，a[0]=3，那么代表正确的数是5时，有三个式子成立，如果您对map不熟悉，可以看我的另一篇文章：

c++ map用法 入门必看 超详细

代码：

#includeusing namespace std;
int main(){int n;
    cin>>n;
    mapa;//map可以按键值升序排序，并且可以离散化数据
    int b[100010]={0};
    for(int i=0;iint c;
        string s;
        cin>>c>>s;
        if(s=="+"){a[0]++;
            a[c]--;
        }
        if(s=="-"){a[c+1]++;
        }
        if(s=="."){a[c]++;
            a[c+1]--;
        }
    }
    int ans=0;
    int k=0;
    for(auto c:a){//离散化后转回数组
        b[k++]=c.second;
    }
    for(int i=0;i<100010;i++){if(i){//前缀和
            b[i]+=b[i-1];
        }
        ans=max(ans,b[i]);//取最优答案
    }
    cout<

#includeusing namespace std;
int main(){int n;
    int a[100010]={0};
    cin>>n;
    for(int i=0;icin>>a[i];
    }
    nth_element(a,a+n/2,a+n);//找到第i大的数，n/2大的数也就是中尾数
    int m=a[n/2];
    int ans=0;
    for(int i=0;ians+=abs(m-a[i]);//其它点到该点的距离
    }
    cout<