P10904（洛谷题面）

题目

题目描述：

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

输入格式：

输入的第一行包含两个正整数 $n,m$ ，用一个空格分隔。

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

输出格式：

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

数据范围与说明：

【样例说明】

路径： $0\to -1\to 0\to 1\to 2$ ，可以对 $\{0,-1,1,2\}$ 四个矿洞挖掘并获得最多 $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$ 。

输入输出样例 #1

输入：

1 2	5 4 0 -3 -1 1 2

输出：

题意

简述：

代码

C

#include <stdio.h>

const int N = 2e6 + 10;
int n,m,l[1000],r[1000],ans,cnt;

int max(int a, int b) {
    return (a > b) ? a : b;
}
int main(){
    
    scanf("%d %d",&n,&m);
    for(int i=1,x;i<=n;i++){
        scanf("%d",&x);
        if(x<0){
            l[-x]++;
        }else if(x>0){
            r[x]++;
        }else{
            cnt++;
        }
    }
    for(int i=1;i<=m;i++){
        l[i]+=l[i-1];
        r[i]+=r[i-1];
    }
    for(int i=1,t;i<=m;i++){
        t=l[i];
        if(m-i*2>0){
            t+=r[m-i*2];
        }
        ans=max(ans,t);
        t=r[i];
        if(m-i*2>0){
            t+=l[m-i*2];
        }
        ans=max(ans,t);
    }
    printf("%d\n",ans+cnt);
    return 0;
}

C++

#include <iostream>

using namespace std;

const int N = 2e6 + 10;
int n,m,l[N],r[N],ans,cnt;

int main(){
    scanf("%d %d",&n,&m);
    for(int i=1,x;i<=n;i++){
        scanf("%d",&x);
        if(x<0){
            l[-x]++;
        }else if(x>0){
            r[x]++;
        }else{
            cnt++;
        }
    }
    for(int i=1;i<=m;i++){
        l[i]+=l[i-1];
        r[i]+=r[i-1];
    }
    for(int i=1,t;i<=m;i++){
        t=l[i];
        if(m-i*2>0){
            t+=r[m-i*2];
        }
        
        
        ans=max(ans,t);
        t=r[i];
        if(m-i*2>0){
            t+=l[m-i*2];
        }
        ans=max(ans,t);
    }
    printf("%d\n",ans+cnt);
    return 0;
}