poj——2566

题目大意

给定一个整数序列（可能包含负数）和一个非负整数目标值 ，要求找到一个连续子序列，使得该子序列和的绝对值最接近 。输出这个绝对值以及子序列的左右端点（下标从1开始，左端点小于等于右端点）。

解题思路

1. 前缀和与排序：

   • 计算前缀和数组 prefix，其中 prefix[0] = 0，prefix[i] = a[1] + a[2] + ... + a[i]。
   • 将前缀和数组按值排序，同时记录每个前缀和对应的原始下标。排序后，任意两个前缀和的差值即为原序列中某一段连续子序列的和。

2. 双指针法：

   • 初始化两个指针 i = 0 和 j = 1，遍历排序后的前缀和数组。
   • 对于当前指针位置，计算差值 cur_sum = prefix[j].value - prefix[i].value（由于已排序，cur_sum >= 0）。
   • 计算 cur_sum 与目标值 t 的绝对差值 diff = abs(cur_sum - t)。
   • 更新最小差值 min_diff，并记录当前最优的子序列和绝对值 best_abs_sum 及对应的原始下标。
   • 移动指针：若 cur_sum < t，则增大 j 以增大差值；否则增大 i 以减小差值。确保 i < j。

3. 确定子序列端点：

   • 根据记录的原始下标 left_idx 和 right_idx，计算子序列的左右端点：
     • start = min(left_idx, right_idx) + 1
     • end = max(left_idx, right_idx)
   • 输出 best_abs_sum、start 和 end。

代码实现

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <climits>
using namespace std;

typedef long long ll;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    ll t;
    while (cin >> n >> t) {
        if (n == 0 && t == 0) break;
        vector<ll> a(n + 1);
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }
        vector<pair<ll, int>> prefix;
        prefix.push_back(make_pair(0, 0));
        ll sum = 0;
        for (int i = 1; i <= n; i++) {
            sum += a[i];
            prefix.push_back(make_pair(sum, i));
        }
        sort(prefix.begin(), prefix.end());

        int i = 0, j = 1;
        ll min_diff = LLONG_MAX;
        ll best_abs_sum = 0;
        int left_idx = 0, right_idx = 0;
        int total = prefix.size();

        while (j < total) {
            ll cur_sum = prefix[j].first - prefix[i].first;
            ll diff = abs(cur_sum - t);
            if (diff < min_diff) {
                min_diff = diff;
                best_abs_sum = cur_sum;
                left_idx = prefix[i].second;
                right_idx = prefix[j].second;
            }

            if (cur_sum < t) {
                j++;
            } else {
                i++;
            }
            if (i == j) {
                j++;
            }
        }

        int start = min(left_idx, right_idx) + 1;
        int end = max(left_idx, right_idx);
        cout << best_abs_sum << " " << start << " " << end << endl;
    }
    return 0;
}

复杂度分析

• 时间复杂度：，主要来自前缀和数组的排序。双指针遍历为 。
• 空间复杂度：，用于存储前缀和数组。