P1956

· · 题解

题目描述

求区间和在模 p 下，大于等于 k 的最小值。

思路

考虑前缀和优化。

(sum[i]-sum[j])\bmod p\geq k

由此得到。

sum[i]-sum[j]\geq k sum[i]-sum[j]+p\geq k

将已知的放到一边，得到。

k-sum[i]\leq -sum[j] k-sum[i]-p\leq -sum[j]

为了快速求出对于每一个 i 对应的最优的解，我们使用 set 动态插入并查询。

代码展示

#include<cstdio>
#include<set>
#define LL long long
using namespace std;

const int MAXN = 1e5 + 5;

int n; LL k, p;
LL a[MAXN], sum[MAXN];
set<LL> s;

int main() {
    scanf("%d%lld%lld",&n, &k, &p);
    for(int i = 1; i <= n; i++)
     scanf("%lld",&a[i]), sum[i] = (sum[i - 1] + a[i]) % p;
    LL res = 5e18; s.insert(0);
    for(int i = 1; i <= n; i++) {
        LL val = *s.lower_bound(k - sum[i]);
        LL now = ((sum[i] + val) % p + p) % p;
        if(now >= k) res = min(res, now);
        val = *s.lower_bound(k - sum[i] - p);
        now = ((sum[i] + val) % p + p) % p;
        if(now >= k) res = min(res, now);
        s.insert(-sum[i]);
    }
    printf("%lld\n",res);
    return 0;
}