题解：P1956 Sum

题目传送门
本人开始算了下数据所以要用

O(n \log n)

和 STL (老师刚教我们)

分析：

给定一个长度为 $n$ 的整数数列 $s$ 的连续子序列的最小长度。如果不存在这样的子序列，则输出 $0$ 。
$S_{i,j}=\sum\limits_{k=i}^ja_k$ 是 $i \sim j$ 之间的和。

核心思想：

前缀和预处理：计算前缀和数组

B

，其中

pre_i = (a_0 + a_1 + \dots + a_{i-1}) \bmod p

。问题转化：对于任意子段

a_{i \sim j}

，其和模 p 的值为

(pre_{j+1} - pre_i) \bmod p

。目标：找到一对

(i, j)

使得

(pre_{j+1} - pre_i) \bmod p ≥ k

，且这个模值尽可能小。

两种情况分析：

对于当前前缀和

C = B[i]

，需要找到之前的前缀和 x 满足：

情况1：如果

C ≥ k

，查找

x \le C - k

的最大值

情况2：查找

x \le C - k + p

的最大值（处理模运算的循环特性）

代码实现

CPP

#include<bits/stdc++.h>
using namespace std;
long long n, k, p;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>k>>p;
    vector<long long> a(n);
    for (long long i = 0; i < n; i++)cin>>a[i];
    vector<long long>B(n+1,0);
    for (long long i = 1;i<= n; i++)B[i]=(B[i-1]+a[i-1])%p;
    long long ans = LLONG_MAX;
    set<long long> s;
    s.insert(0); 
    for (long long i = 1; i <= n; i++){
        long long current = B[i];
        // 我们需要找到 x 使得 (current - x) % p >= k
        // 等价于找到 x <= current - k 或者 x <= current - k + p
        // 情况1: 查找 x <= current - k
        if (current >= k) {
            long long target=current-k;
            set<long long>::iterator it=s.upper_bound(target);
            if (it != s.begin()) {
                it--;
                long long mod_val=(current - *it) % p;
                if (mod_val>=k) {
                    ans = min(ans, mod_val);
                }
            }
        }
        // 情况2: 查找 x <= current - k + p
        long long target2=current-k+p;
        set<long long>::iterator it2 = s.upper_bound(target2);
        if (it2 != s.begin()) {
            it2--;
            long long mod_val = (current-*it2 + p) % p;
            if (mod_val >= k) {
                ans = min(ans, mod_val);
            }
        }
        s.insert(B[i]);
        // 提前退出优化
        if (ans == k) {
            break;
        }
    }
    cout << ans << endl;
    return 0;
}

注意事项

边界处理：代码初始时将

ans

设为

2^{63}-1

，但未处理无解情况（应输出

0

）。

模运算特性：充分利用模运算的循环性质，通过两种情况覆盖所有可能。

提前退出：当找到最优解

ans = k

时立即退出循环，优化性能。

集合维护：使用 set 保持元素有序，便于二分查找。

求个赞，谢谢！！

文章操作

分析：