题解：P16857 [GKS 2021 #F] Trash Bins

· · 题解

题解：P16857 [GKS 2021 #F] Trash Bins

题目传送门

一道适合入门新手的题，有一点点的思维需求（不会很多，大部分人应该都能看懂）。

算法标签

字符串、循环、数组。

题目大意

给定 N 个点，其中有若干个点有垃圾桶，求每一个点到其最近的垃圾桶的距离之和。

具体思路

暴力

很容易发现，一个点的答案贡献一定是左右两边最近的垃圾桶（若存在）的距离的较小值，那么可以对于每一个点分别往左边和右边循环查找最近的垃圾桶，算出距离累加答案。但是这个时间复杂度不够优秀，在极端数据下处理单次数据的时间复杂度可能高达 O(N^2)（垃圾桶仅在 1 号节点和 N 号节点），在 1 \le N \le 5 \times 10^5 的数据范围下无法通过，所以需要寻找更优的解法。

正解

照着暴力的思路，我们发现时间过大的主要原因是每次都要枚举左边/右边的位置来找到垃圾桶，很多没有垃圾桶的位置会重复枚举，所以我们可以尝试将所有点的左边/右边最近的垃圾桶一起计算处理。先考虑左边，我们可以使用一个 last 变量存储上一个垃圾桶的位置，res_i 存储从左边到位置 i 最近的垃圾桶的距离。每当枚举到一个位置时，如果有垃圾桶，则更新 last 的值为当前位置，当前位置的 res 值为 0；否则，根据原题面中给出的距离公式可以得出当前的 res 值为 i-last，如果 last 还没有计算过，则其值为 0x3f3f3f3f。同理，也可算出右边最近的垃圾桶距离。对于每一个位置，将两个值取小累加进 ans 变量，最后输出 ans 即可。

正解复杂度分析

时间复杂度

我们需要先正序枚举维护 res 数组，这部分的时间复杂度 O(N)。再逆序枚举算出右边最近的垃圾桶距离，统计答案，这部分的时间复杂度同为 O(N)。二者合并化简，可得处理单次数据的时间复杂度为 O(N)，在 1 \le N \le 5 \times 10^5 的数据范围下可以轻松跑过。

空间复杂度

处理过程中我们需要维护一个 res 数组，此外无需额外的需耗费较大空间量的变量，所以空间复杂度为 O(N)，满足题目限制。

总体来说，这个解法时间和空间性能都较好，常数也较小，十分优秀。

具体实现

实现细节

首先，ans 变量需要开long long。因为 N 最大可达到 5 \times 10^5，而答案最大可达到约 N^2 左右，也就是 2.5 \times 10^{11} 左右，远超int所能表示的范围（约 2 \times 10^9 左右），所以要开long long。

其次，为了方便我们大部分人从 1 开始下标的习惯，输入进来的字符串需要在前面加上一个空格（或者其他字符）来保证下标相互匹配。

再次，我们每个点的右边最近的垃圾桶距离可以不用数组存储，因为我们可以在边计算的时候边统计答案，既优化了空间又提升了时间性能（可以少一次循环）。

最后，要根据题目中的格式输出，不要只输出一个 ans 变量！

参考代码

::::success[AC code] 这段代码是我在写下这篇题解时的最优解（即 2026.6.11），以 92 ms 的运行时间领先第三名 18 ms（第二名暂时无法查看），可以看出这段代码的优秀。

AC 记录

马蜂微丑，请见谅。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e5+10;
int res[MAXN];
int t;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);//关闭同步流。
    cin>>t;
    for(int Case=1;Case<=t;Case++){//循环处理每一组数据。
        int n;
        string s;
        cin>>n>>s;
        s=" "+s;//对齐下标。
        int last=0;
        for(int i=1;i<=n;i++){//正序处理左边最近的垃圾桶距离。
            if(s[i]=='1'){//如果该位置有垃圾桶。
                res[i]=0;
                last=i;//更新最近垃圾桶位置。
            }else{
                if(last==0){
                    res[i]=0x3f3f3f3f;
                }else{
                    res[i]=i-last;
                }
            }
        }
        last=n+1;//也可以换成 0，但是第 35 行的 n+1 也要随之更改。
        long long ans=0LL;//注意开 long long。
        for(int i=n;i>=1;i--){//逆序处理右边最近的垃圾桶距离。
            if(s[i]=='1'){//如果该位置有垃圾桶。
                last=i;//更新最近垃圾桶位置。
            }else{
                if(last==n+1){
                    ans+=res[i];
                }else{
                    ans+=min(res[i],last-i);//取小并加入最终答案。
                }
            }
        }
        cout<<"Case #"<<Case<<": "<<ans<<endl;//输出答案，注意格式。
    }
    return 0;//好习惯。
}

:::: 完结撒花！