火星购物

思想：

• 前缀和，双指针。
  • 快指针 i 作为某一分割区间的右端点，慢指针 j 作为该区间的左端点。
  • 当 a[i] - a[j + 1] >= m 时，将 j 右移，以尝试缩小区间并使区间和更接近 m。
  • 每次移动后判断 a[i] - a[j] 的值：
    • 若 a[i] - a[j] == m，说明找到了和恰好为 m 的区间 [j+1, i]，输出并标记。
    • 若 a[i] - a[j] > m，说明当前区间和大于目标，但可能比之前更接近，因此更新最小差值 ans。
  • 第一轮遍历旨在找到精确解或记录最接近的和。
  • 若未找到精确解，则进行第二轮遍历，输出和等于第一轮记录的最小差值 ans 的区间。

代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 3;
typedef long long LL;

LL a[N];
// ans 记录最接近 m 的区间和与 m 的最小差值
LL ans = 0x3f3f3f3f;

void solve() {
    int n, m; cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i] += a[i - 1]; // 计算前缀和
    }
    
    bool found_exact = false;
    // 第一轮遍历：寻找精确解或更新最接近的和
    for (int i = 1, j = 0; i <= n; i++) {
        // 移动左指针 j，使区间 (j, i] 的和尽可能接近但可能大于 m
        while (a[i] - a[j + 1] >= m && j < i) j++;
        
        LL current_sum = a[i] - a[j];
        if (current_sum == m) {
            // 找到和恰好为 m 的区间 [j+1, i]
            cout << j + 1 << '-' << i << endl;
            found_exact = true;
        } else if (current_sum > m) {
            // 当前区间和大于 m，更新与 m 的最小差值
            ans = min(ans, current_sum - m);
        }
    }
    
    // 第二轮遍历：如果没有找到精确解，则输出和等于 (m + ans) 的区间
    if (!found_exact) {
        LL target = m + ans;
        for (int i = 1, j = 0; i <= n; i++) {
            while (a[i] - a[j + 1] >= target && j < i) j++;
            if (a[i] - a[j] == target) {
                cout << j + 1 << '-' << i << endl;
            }
        }
    }
}

int main() {
    solve();
    return 0;
}