浙大PAT_1044：Shopping in Mars 答题报告

浙大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。

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

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

#include <stdio.h>#define N 100001#define M 100000001int main(){int n, m, i, j;int a[N];int sum, tmp, cnt, jmp;int b[N][2];while (scanf("%d%d", &n, &m) != EOF){for (i = 1; i <= n; i++){scanf("%d", &a[i]);}sum = M;cnt = 0;jmp = 0;for (i = 1; i <= n; i++){tmp = 0;for (j = i + jmp; 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++;}if (tmp == m && j - i > 1){jmp = j - i - 1;}else {jmp = 0;}break;}}if (tmp == m && j == n)break;}for (i = 0; i < cnt-1; i++){printf("%d-%d\n", b[i][0], b[i][1]);}printf("%d-%d", b[i][0], b[i][1]);}return 0;}