文章目录
题目大意思路AC代码
题目大意
求一串的数字中连续的一段，使得这个区间内数字的和恰好等于给定值m；如果不能找到恰好等于m，就找到总和大于m且与m之差最小的区间。求所有可能的区间结果。
思路
直接模拟会超时。 注意到我们要求的是连续和的问题。建立一个数组sum，sum[i]为第1个数到第i个数的和，可知sum数组是单调递增的；而第i个数到第j个数的和等于sum[j]-sum[i-1]。这样我们就可以对sum数组用二分查找法了。固定区间左端点，在sum数组中用二分法寻找合适的右端点，找到大于等于且最接近m的值（因数组元素均为正数，所以值实际上是唯一的）。左端点遍历一遍，就可以找到所有答案啦。
AC代码
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<math.h>
#include<vector>
#include<algorithm>
using namespace std
;
#define MAX 402
#define INF 100000000
int n
, m
, nearest
= INF
;
struct node
{
int u
, v
;
};
vector
<int>sum
;
vector
<node
>ans
;
void BinarySearch(int left
, int right
) {
int mid
, cut
= left
;
while (left
< right
) {
mid
= (left
+ right
) / 2;
if (sum
[mid
] - sum
[cut
] >= m
)right
= mid
;
else left
= mid
+ 1;
}
if (sum
[right
] - sum
[cut
] >= m
) {
if (sum
[right
] - sum
[cut
] - m
== nearest
)
ans
.push_back({ cut
,right
});
if (sum
[right
] - sum
[cut
] - m
< nearest
) {
ans
.clear();
ans
.push_back({ cut
,right
});
nearest
= sum
[right
] - sum
[cut
] - m
;
}
}
}
int main() {
int i
, a
;
scanf("%d%d", &n
, &m
);
sum
.resize(n
+ 1);
sum
[0] = 0;
for (i
= 1; i
<= n
; i
++) {
scanf("%d", &a
);
sum
[i
] = sum
[i
- 1] + a
;
}
for (i
= 0; i
<= n
; i
++)
BinarySearch(i
, n
);
for (i
= 0; i
< ans
.size(); i
++)
printf("%d-%d\n", ans
[i
].u
+ 1, ans
[i
].v
);
return 0;
}
