自动搬运

查看原文

来自洛谷，原作者为

	Leap_Frog 是啊……你就是那只鬼了……所以被你碰到以后，就轮到我变成鬼了

搬运于2025-08-24 21:32:17，当前版本为作者最后更新于2020-07-20 19:39:37，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

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;//输出答案，完结撒花
}```