浙大PAT_1044：Shopping in Mars 解题报告

题目大意：给出长度为n的一个整数序列，找出其中所有和为m的子序列（连续的），如果没有任何子序列的和等于m，那么找出大于m的最小和。如长度为8的序列3，2，1，5，4，6，8，7，找出和为15的子序列有三个：1~5，4~6，7~8。

这道题思路并不难，一般都能想到通过遍历来解决，但是如果不注意细节是很难拿到满分的。

以下是大家通常能够写出的解决方法：

[cpp]

#include <iostream>

using namespace std;

#define N 100001 //由于个人电脑的内存限制，在个人电脑上测试时需减小该值，提交时再改为此值

#define M 100000001

int main()

{

int n, m, i, j;

int a[N];

int sum, tmp, cnt;

int b[N][2]; //存储结果

while (cin >> n >> m)

{

for (i = 1; i <= n; i++)

{

cin >> a[i];

}

sum = M;

cnt = 0;

for (i = 1; i <= n; i++)

{

tmp = 0;

for (j = i; j <= n; j++)

{

tmp += a[j];

if (tmp >= m)

{

if (tmp < sum)

{

cnt = 0;

sum = tmp;

b[cnt][0] = i;

b[cnt][1] = j;

cnt++;

}

else if (tmp == sum)

{

b[cnt][0] = i;

b[cnt][1] = j;

cnt++;

}

break;

}

for (i = 0; i < cnt-1; i++)

{

cout << b[i][0] << '-' << b[i][1] << endl;

}

cout << b[cnt-1][0] << '-' << b[cnt-1][1];

}

return 0;

}

用惯了C++的人可能会很熟练地就把个程序给写出来了，但是，提交后发现有三个case超时。所以，基本的“暴力”解决方法是不行的，当然，如果是考试那么做到这一步可以先往下进行了，如果有时间再回过头来优化。然而，刷题的童鞋们都知道，哪怕是差一分这道题都不能叫通过，题目列表前面都不会出现“Y”，很多人看着会很不爽（可能有点易做图症）。所以想办法继续优化吧。

（如果没有耐心看思路分析，那么直接看下面的程序吧！）

上面程序的时间复杂度为O(n^2)，看看能不能找到O(logn)的解决办法，这个有点难哦！

如果不能在本质上改变程序的时间复杂度，那么看看在O(n^2)的基础上对程序的细节进行优化。仔细分析在遍历的过程中，内层循环可以跳过某些元素，比如当p~q的元素和刚好等于m时，那么下次从p+1开始寻找时，(p+1)~q内的元素和肯定小于m，那么直接从q往后依次增加元素就可以了。

于是，得到了以下可以跳过某些序列的优化程序：