第一题:

2566:Bound Found

题目链接：

P2566——Bound Found——柒行（www.oj7.cn）

题目来源：

Ulm Local 2001

题目描述

总时间限制:

5000ms

内存限制:

65536kB

Description

Signals of most probably extra-terrestrial origin have been received and digitalized by The Aeronautic and Space Administration (that must be going through a defiant phase: "But I want to use feet, not meters!"). Each signal seems to come in two parts: a sequence of n integer values and a non-negative integer t. We'll not go into details, but researchers found out that a signal encodes two integer values. These can be found as the lower and upper bound of a subrange of the sequence whose absolute value of its sum is closest to t.

You are given the sequence of n integers and the non-negative target t. You are to find a non-empty range of the sequence (i.e. a continuous subsequence) and output its lower index l and its upper index u. The absolute value of the sum of the values of the sequence from the l-th to the u-th element (inclusive) must be at least as close to t as the absolute value of the sum of any other non-empty range.

输入

The input file contains several test cases. Each test case starts with two numbers $n$ and $k$. Input is terminated by $n=k=0$. Otherwise, $1<=n<=100000$ and there follow $n$ integers with absolute values $<=10000$ which constitute the sequence. Then follow $k$ queries for this sequence. Each query is a target $t$ with $0<=t<=1000000000$.

输出

For each query output $3$ numbers on a line: some closest absolute sum and the lower and upper indices of some range where this absolute sum is achieved. Possible indices start with $1$ and go up to $n$.

输入数据

5 1
-10 -5 0 5 10
3
10 2
-9 8 -7 6 -5 4 -3 2 -1 0
5 11
15 2
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
15 100
0 0

输出数据

5 4 4
5 2 8
9 1 1
15 1 15
15 1 15

中文题面：

描述

美国宇航局（目前似乎正处于叛逆期："我就要用英尺，不要米！"）接收并数字化了一系列大概率来自地外文明的信号。 每个信号由两部分组成：一个包含$n$个整数值的序列和一个非负整数$t$。 具体细节暂不赘述，但研究人员发现，每个信号实际编码了两个整数值，这两个值对应序列中某个连续子序列的和的绝对值最接近$t$时的子序列起始和结束位置。 输入要求 给定一个包含$n$个整数的序列和一个非负目标值$t$。 输出要求 找出一个非空连续子序列（即序列的连续子区间），输出其起始索引$l$和结束索引$u$。要求该子序列（从第$l$个元素到第$u$个元素，包含两端）的绝对和值与$t$的接近程度不劣于任何其他非空连续子序列的绝对和值与$t$的接近程度。 关键点说明 连续子序列（continuous subsequence）指序列中相邻元素的连续区间，例如序列$[a,b,c,d]$中的$[b,c]$。 "绝对和值最接近$t$"的数学含义为：在所有可能的非空子序列中，满足$|sum|$与$t$的差值最小。 若存在多个满足条件的子序列，通常需输出索引范围最小的（或根据题目隐含规则选择首个出现的解）。 输入说明 输入文件包含多个测试用例。每个测试用例以两个整数$n$和$k$开头。输入以$n=k=0$结束，其余情况下满足 $1<=n<=100000$ 。接下来是构成序列的$n$个整数（每个数的绝对值不超过$10000$），随后是$k$个针对该序列的查询。每个查询给出一个目标值$t$，满足$0<=t<=1000000000$。 输出要求 对于每个查询，输出一行三个数：某个最接近的绝对和值，以及该和值对应的子区间的起始索引$l$和结束索引$u$。索引从$1$开始，最大为$n$。 关键点说明 输入以 $n=k=0$ 结束，程序需正确处理这一终止条件。输出中的“某个最接近的绝对和值”意味着可能存在多个子区间满足条件，输出任意一个合法解即可。索引从$1$开始计数，例如序列 $[a,b,c]$ 的完整索引范围为$1——3$。

输入数据

5 1
-10 -5 0 5 10
3
10 2
-9 8 -7 6 -5 4 -3 2 -1 0
5 11
15 2
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
15 100
0 0

输出数据

5 4 4
5 2 8
9 1 1
15 1 15
15 1 15

算法标签

前缀和 二分查找

解题思路：

计算数组的前缀和，将连续子数组的和转化为两个前缀和的差。维护一个有序集合，保存已处理的前缀和及其索引，确保在插入新元素时能快速查找。对于每个前缀和，通过二分查找在有序集合中找到最接近目标的候选值，从而快速确定最优子数组。针对每个查询值$t$分别处理正负两种情况，确保覆盖所有可能的最近邻解。

实现步骤：

输入处理：

读取输入数据。

前缀和计算：

预处理数组的前缀和数组 $s$。

查询处理：

对每个查询 $t$，遍历前缀和数组，维护有序集合，查找最优解。

插入与更新：

插入当前前缀和到有序集合，并确保相同值时保留最大索引。

输出结果： 根据最优解输出绝对和、起始和结束索引。

C++实现：

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int inf=0x3f3f3f3f; // 定义无穷大的常量
const int M=1e5+10;       // 定义数组最大容量

int n,m,k,l,r,x,y,ans,mi; // 全局变量声明

// 结构体定义，保存前缀和及其对应的原始下标
struct node {
    int id;   // 原始数组中的位置（从1开始）
    int sum;  // 前缀和
} s[M];      // 前缀和数组

// 自定义排序规则：按前缀和升序排列
bool cmp(node x, node y) {
    return x.sum < y.sum;
}

// 处理单个查询的函数
void solve() {
    l = 0; r = 1; mi = inf; // 初始化左右指针和最小差值
    // 双指针遍历排序后的前缀和数组
    while (l <= n && r <= n && mi != 0) {
        int temp = s[r].sum - s[l].sum; // 计算当前区间和
        // 如果当前差更接近目标值k，则更新最优解
        if (abs(temp - k) < mi) {
            mi = abs(temp - k);
            x = s[l].id;
            y = s[r].id;
            ans = temp;
        }
        // 根据当前区间和与目标值的关系调整指针
        if (temp > k) l++;     // 区间和太大，左指针右移
        else if (temp < k) r++; // 区间和太小，右指针右移
        else break;            // 完全匹配，提前终止
        // 避免左右指针重合
        if (r == l) r++;
    }
    // 确保输出的起始下标小于等于结束下标
    if (x > y) swap(x, y);
    // 输出结果（下标从1开始）
    printf("%d %d %d\n", ans, x + 1, y);
}

int main() {
    // 多测试用例处理，直到输入n=0且m=0
    while (~scanf("%d%d", &n, &m)) {
        if (n == 0 && m == 0) break;
        s[0].sum = s[0].id = 0; // 初始化前缀和数组的起点
        // 读取原始数组并构建前缀和数组
        for (int i = 1; i <= n; i++) {
            scanf("%d", &s[i].sum);
            s[i].sum += s[i - 1].sum; // 累加前缀和
            s[i].id = i;              // 记录原始位置
        }
        // 对前缀和数组进行排序（包含第0项）
        sort(s, s + 1 + n, cmp);
        // 处理每个查询
        while (m--) {
            scanf("%d", &k); // 读取目标值k
            solve();         // 求解并输出结果
        }
    }
    return 0;
}