被束缚
题目给出一串数据,比如 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)
