題目大意：給出長度為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往後依次增加元素就可以了。 於是，得到了以下可以跳過某些序列的優化程序： [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, jmp; int b[N][2]; while (cin >> n >> m) { for (i = 1; i <= n; i++) { cin >> 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++) { cout << b[i][0] << '-' << b[i][1] << endl; } cout << b[cnt-1][0] << '-' << b[cnt-1][1]; } return 0; } 但是提交後發現，還是有一個用例超時…… 實在不知有哪些步驟可以再省略了，記得C語言的輸入輸出要比C++高效些，把cin，cout換成scanf，printf試試，結果還真通過了！這道題給的時間限制真是剛好，測試用例設計的真是“高”！ 最終，AC的程序如下： [cpp] #include <stdio.h> #define N 100001 #define M 100000001 int 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; } www.2cto.com 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; }
