被束缚

链接

题目给出一串数据,比如 2 -23 44 124 -51 32 34 5 并给出目标数据t(t>0),要求我们找到一个子序列(或者一个区间),使得这个子序列的和的绝对值最接近t,并输出和的绝对值和 左区间和右区间

我们假设t为89,我们可以找到最接近的数为94,从2到5,也就是 94 2 5

这题乍一看是滑动窗口,但似乎又不太好滑,主要还是因为窗口大小未知,如果直接滑要n!次,非常大。所以我们需要找到一方法,排好序(因为原序列是乱的,往右加总和不确定),如果单调增加或单调减少,那么我们就可以减少遍历次数了

但如果直接排序的话,我们会发现得到的结果不连续(即最终区间是断开的)

解决该问题的其中一个思路是求前缀和,我们可以先求从1开始到结尾相加的和 比如 1 -2 3 -5 6 -10 其前缀和为1(1) -1(2) 2(3) -3(4) 3(5) -7(6) 括号内是编号

我们再对其进行排序 -7(6) -3(4) -1(2) 1(1) 2(3) 3(5) 我们发现右边的数减左边就是从小序号+1到大序号的和,比如(-3)-(-7)=4就是5~6的和

越是靠近右边,减去的结果越大,因为序列单调增加

思路有了,代码实现如下

#include<iostream>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
struct Node {
	int sum;
	int index;
	bool operator<(const Node& other) const {
		if (sum == other.sum) return index < other.index;
		return sum < other.sum;
	}
};
int main() {
	int n, k;
	while (cin >> n >> k && (n || k)) {
		vector<int>num(n);
		for (int i = 0;i < n;i++) {
			cin >> num[i];
		}
		vector<Node>pre(n + 1);
		pre[0] = { 0,0 };
		int sum = 0;
		for (int i = 1;i < n + 1;i++) {
			sum += num[i - 1];
			pre[i] = { sum,i };
		}
		sort(pre.begin(), pre.end());
		while (k--) {
			int t;
			cin >> t;
			int best_sum=0;
			int best_l = 0, best_r = 0, left = 0;
			int min_diff = 2e9;
			for (int right = 1;right <= n;) {
				int diff = abs(pre[right].sum - pre[left].sum);
				if (abs(diff - t) < min_diff) {
					min_diff = abs(diff - t);
					best_sum =diff;
					best_l = min(pre[left].index, pre[right].index) + 1;
					best_r = max(pre[left].index, pre[right].index);
				}
				if (diff < t) {
					right++;
				}
				else if (diff > t) {
					left++;
				}
				else {
					break;
				}
			}
			cout << best_sum<<" "<< best_l << " " << best_r << " " << endl;
		}
	}
}

时间复杂度:O(n log n + k * n)

空间复杂度:O(n)