水题，甚至比我做的很多绿都简单。也许是比较典？
套路的，设数组 \(b\) 满足 \(b_i =a_i\bmod p\)。相当于求 \(b\) 的在模 \(p\) 意义下最小大于 \(k\) 子段和。
更加套路的，我们有前缀和优化的 \(n^2\) 做法：枚举左右端点。
但是显然在 \(n\le 10^5\) 时这做法寄了。
我们换个思路：如果只要求大于 \(k\) 的值，那么是否一些枚举是不必要的？
没错确实有很多不必要的枚举。我们枚举右端点 \(r\)，寻找一个最大的 \(l\) 使得这个区间满足要求。这样直接一路 \(O(n)\) 扫过去就可以了。
但是怎么找呢？把前缀和丢进 set 就行了。
总复杂度 \(O(n\log n)\)。
然后这道题就基本做完了。
小心两个坑点：
- 别忘了
long long。 - 直接减会出负数。
#include <set>
#include <stdio.h>
#include <algorithm>
#define int long long
using std::min;
std::set<int> q;
int s[100005];
signed main()
{q.insert(0);
int n,k,p,i,x,res=1ll<<60;scanf("%lld %lld %lld",&n,&k,&p);
for(i=1;i<=n;++i)
{
scanf("%lld",&x);
s[i]=(s[i-1]+x)%p;
}
for(i=1;i<=n;++i)
{
res=min(res,s[i]+(s[i]<k?p:0)-(*--q.upper_bound((s[i]+p-k)%p)));
q.insert(s[i]);
}
printf("%lld",res);
return 0;
}