题解 P10904

HYdroKomide · 2024-08-24 19:48:23 · 题解

题意：

在数轴上以原点为中心移动，一些点有分数（只能获取一次），走 m 步能获取多少分数。

思路：

首先，走回头路总是劣的。因此，只有四种可能的方案：正方向走到头、反方向走到头、反方向走 t 格然后往正方向走到头、正方向走 t 格然后往反方向走到头。

发现前两个方案可以与后两个方案合并。所以实际要求的就是枚举 t\le m 的情况下这个式子的最大值：

其中 l_i 代表负半轴走 t 距离的分数，r_i 表示正半轴同理。

前缀和分别求出 l,r，模拟即可。注意特判零点有分的情况。

程序如下：

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=2e6+5;
int n,m,prel[N],prer[N],ans;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        int x;
        scanf("%d",&x);
        if(x>0)prer[x]++;
        else if(x==0)prer[x]=prel[x]=1;//零点的分数在左右都要算
        else prel[-x]++;
    }
    for(int i=1;i<=1e6;i++)prel[i]=prel[i]+prel[i-1],prer[i]=prer[i]+prer[i-1];
    for(int i=0;i<=m;i++){
        if(i*2>m){
            ans=max(ans,prer[i]+prel[0]);
            ans=max(ans,prel[i]+prer[0]);
        }
        else{
            ans=max(ans,prer[i]+prel[m-i*2]);
            ans=max(ans,prel[i]+prer[m-i*2]);
        }
    }
    printf("%d\n",ans-prer[0]);//注意因为左右都算了，最后再减去零点的分数即可
    return 0;
}

THE END