P1956Sum（题解）

· · 题解

P.S.

此题应该挺经典的，但是我还是不会。

Problem.

给定一个序列，找出在所有子串和对p取模意义下的大于等于k的最小值。

Solution.

首先，我们有一个很显然的暴力做法，复杂度为O(N^3)（废话。
即我们枚举所有子串和，找到最小值，对于本题很显然超时。

这题也有一个很显然的优化思路，即用前缀和。
记s[i]=\sum_{j=1}^ia[i]，则a[i]+...+a[j]=s[j]-s[i-1]。（废话。
所以这样可以O(1)计算连续子串和，复杂度降为了O(N^2)。

我们来仔细分析以下这个暴力慢在哪里了。
对于一个节点，以其为结尾的子串只需要找到那个子串和最接近。
即要找到一个s[j]最接近s[i]-k的，而且要小于s[i]-k的。

那么此题思路就很清晰了。
我们可以用set来维护所有s[j](j\le i)，对于每个序列，直接查找不大于s[i]-k的最大值就好了。
而查找可以用upper_bound，引入了一个set，复杂度变成了O(N\times \log N)。

完结撒花，无耻求赞。

Coding.


#include<bits/stdc++.h>
using namespace std;
int n,k,p,ans=1e9,s[100005];set<int>e;//定义
int main()
{
    scanf("%d%d%d",&n,&k,&p),s[0]=0,e.insert(0);//读入，初始化
    for(int i=1,x;i<=n;i++) scanf("%d",&x),s[i]=(s[i-1]+x)%p;//求前缀和
    for(int i=1;i<=n;i++)
    {//求的是%p意义下的小于，要分情况讨论
        if(s[i]>=k) ans=min(ans,s[i]-(*--e.upper_bound(s[i]-k)));
        else ans=min(ans,s[i]+p-(*--e.upper_bound(s[i]-k+p)));
        e.insert(s[i]);//插入新来的s[i]
    }
    return printf("%d\n",ans),0;//输出答案，完结撒花
}```