自动搬运

查看原文

来自洛谷，原作者为

	WardLee _________________________________

搬运于2025-08-24 22:37:06，当前版本为作者最后更新于2022-03-23 17:06:40，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意：

一个人吃豆豆，沿路上有若干段豆豆，这个人挨着吃，吃 $k$ 个就会立马吐光继续吃。某些相邻两段之间有垃圾桶，这个人可以选择一段不吃，问最多往垃圾桶里吐几次。

假设每一段都有豆豆。

首先考虑不能不吃的情况：

将每段豆豆数量做前缀和，统计有垃圾桶且前缀和模 $k$ 等于0的位置数。

再加上可以有一段不吃的情况：

枚举跳过的一段，如果后面某一个位置的前缀和减去这段豆豆数后模 $k$ 的值为 $0$， 那么它模 $k$ 就等于这段豆豆数模 $k$。所以这一段后面统计前缀和模 $k$ 等于 这段豆豆数模 $k$ 的位置数，这一段前面仍然只统计前缀和模 $k$ 等于 $0$ 的位置数(均有垃圾桶)，二者相加即可。

由于 $k$ 只有 $10^6$，开两个大小为 $10^6$ 的数组 $l$ 和 $r$，$l[i]$ 和 $r[i]$ 分别存储某一段前面和后面有垃圾桶且前缀和模 $k$ 为 $i$ 的位置数。假定这段初始时为 $0$ 或 $n+1$，则先把全部有垃圾桶且前缀和模 $k$ 为 $i$ 的位置数储存在 $r[i]$ 或 $l[i]$ 中，从前往后或从后往前边枚举跳过的一段，边更新 $l$ 和 $r$ 和答案即可。

计算时若某一段无豆豆，则跳过，不用其前缀和更新。

时间复杂度：$O(n)$

代码：

#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

typedef long long LL;

const int N = 300010, M = 1000010;
int n, m;
LL a[N], s[N], res, K;
int nl[M], nr[M];
bool st[N];

int main(){
    scanf("%d%d%lld", &n, &m, &K);
    for(int i = 1; i <= m; i ++){
        int t;
        scanf("%d", &t);
        st[t] = true;
    }

    for(int i = 1; i <= n; i ++){
        scanf("%lld", &a[i]);
        s[i] = a[i] + s[i - 1];
        if(a[i] && st[i]) nl[s[i] % K] ++;
    }

    int res = nl[0];
    for(int i = n; i >= 1; i --){
        if(a[i] && st[i]) nl[s[i] % K] --;
        res = max(res, nl[0] + nr[a[i] % K]);
        if(a[i] && st[i]) nr[s[i] % K] ++;
    }
    printf("%d\n", res);
    return 0;
}