[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