[PAT解题报告] Shopping in Mars
给定一个数组，每个数都是正数，求所有子数组和等于m，如果没有这样的子数组，求所有子数组和大于m并且最小。换言之，就是求所有的子数组和>=m,并且最小。
滑动窗口经典题，因为所有的数都是正数，所以如果小的数组的和小于m，则它的子数组的和全部小于m。于是我们可以动态维护窗口里的值，并且不断滑动。当然也可以保存前缀和sum[i]
= a[1] + a[2] +... + a[i] (下标从1开始），则子数组[i..j]对应于sum[j] - sum[i -
1]。我们维护窗口[i..j]的和，如果它小于m，则扩大它++j, 如果它和大于m，则减小它++i,
这样我们利用O(n)的时间可以求出全部的合法窗口。
代码：
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;
int sum[100005];
int main() {
int n,m;
scanf("%d%d",&n,&m);
int j = 0, may = 2000000000;
bool have = false;
for (int i = 1; i <= n; ++i) {
int x;
scanf("%d",&x);
sum[i] = sum[i - 1] + x;
for (; sum[i] - sum[j] > m; ++j)
;
if (sum[i] - sum[j] == m) {
printf("%d-%d\n", j + 1, i);
have = true;
}
if ((j) && (sum[i] - sum[j - 1] > m)) {
may = min(may, sum[i] - sum[j - 1]);
}
}
if (!have) {
m = may;
j = 0;
for (int i = 1; i <= n; ++i) {
for (;sum[i] - sum[j] > m; ++j)
;
if (sum[i] - sum[j] == m) {
printf("%d-%d\n", j + 1, i);
}
}
}
return 0;
}
原题链接： http://www.patest.cn/contests/pat-a-practise/1044
投递万得信息等公司10个岗位 >