问题描述

小蓝正在数轴上挖矿，数轴上一共有 $n$ 个矿洞，第 $i$ 个矿洞的坐标为 $a_i$。小蓝从 $0$ 出发，每次可以向左或向右移动 $1$ 的距离。当路过一个矿洞时，就会进行挖矿作业，获得 $1$ 单位矿石。但一个矿洞不能被多次挖掘。小蓝想知道在移动距离不超过 $m$ 的前提下，最多能获得多少单位矿石？

输入格式

输入的第一行包含两个正整数 $n, m$，用一个空格分隔。
第二行包含 $n$ 个整数 $a_1, a_2, \cdots, a_n$，相邻整数之间使用一个空格分隔。

输出格式

输出一行包含一个整数表示答案。

样例输入

Plaintext

5 4
0 -3 -1 1 2

样例输出

Plaintext

4

样例说明

路径：$0 \to -1 \to 0 \to 1 \to 2$，可以对 $0, -1, 1, 2$ 四个矿洞挖掘并获得最多 $4$ 块矿石。
_(注：距离计算为 $0 \to -1$ (1) $\to 0$ (1) $\to 1$ (1) $\to 2$ (1)，总距离 4，不超过 $m=4$)_

评测用例规模与约定

对于 $20\%$ 的评测用例，$1 \le n \le 10^3$。
对于所有评测用例，$1 \le n \le 10^5$，$-10^6 \le a_i \le 10^6$，$1 \le m \le 2 \times 10^6$。

枚举尽可能往左走和尽可能往右走的情况

#include<iostream>
#include<vector>
using namespace std;
const int MAX_COORD = 2000005;
vector<int>arr(4000011,0);
int minlocation=2000005,maxlocation=2000005,lmaxvalue=0,rmaxvalue=0;
int main(){
    int m,n;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int a;
        cin>>a;
        arr[a+MAX_COORD]+=1;
    }
    for(int i=1;i<=4000010;i++)
        arr[i]+=arr[i-1];
        for(int i=0;i<=m/2;i++)
        {
            if((arr[MAX_COORD]-arr[MAX_COORD -i-1]+arr[MAX_COORD+m-2*i]-arr[MAX_COORD])>lmaxvalue)
            lmaxvalue=arr[MAX_COORD]-arr[MAX_COORD -i-1]+arr[MAX_COORD+m-2*i]-arr[MAX_COORD];
        }
        for(int i=0;i<=m/2;i++)
        {
             if((arr[MAX_COORD+i]-arr[MAX_COORD-1]+arr[MAX_COORD-1]-arr[MAX_COORD-m+2*i-1])>rmaxvalue)
            rmaxvalue=arr[MAX_COORD+i]-arr[MAX_COORD-1]+arr[MAX_COORD-1]-arr[MAX_COORD-m+2*i-1];
        }
        cout<<max(lmaxvalue,rmaxvalue);
    }