題目：在一個由N個整數組成的數列中，最多能找到多少個位置連續的整數且其中的最大值與最小值之差不超過K呢？

GDKOI 2003 又一道很類似的題（河床）使用的是動態規劃，因為數據范圍較小（復雜度為O(nk)），這里10^6*10^6肯定超時（確實TLE了）；

這里使用一次掃描，加上單調隊列，將復雜度降為O(n)（每個元素最多只進隊一次，最多只出隊一次），當然不是自己的思路……詳見“CSU_BMW正式組建紀念賽”解題報告以及COJ1170(A Simple Problem)這兩篇，LJ大牛的代碼比較清晰；

WA無數次，TLE多次，RE兩次，魔法值-50。。。

# include <stdio.h># define MAXN 1000005int n, k; int t[MAXN]; int Q[2][MAXN], f[2], r[2]; /* Q[0]:rise, Q[1]:fall */int cmp_ll(int x, int y, int b) {long long xx = x;long long yy = y;long long bb = b; if (xx>=yy && xx-yy<=bb) return 1;if (xx<=yy && yy-xx<=bb) return 1;return 0; }int main() {int i, j, len, ans;while (~scanf("%d%d", &n, &k)){for ( i = 1; i <= n; ++i)scanf("%d", &t[i]);f[0] = r[0] = 0;f[1] = r[1] = 0;Q[0][r[0]++] = 1;Q[1][r[1]++] = 1;ans = 1;i = j = 1;while (j < n){ while (j<n && cmp_ll(t[Q[0][f[0]]], t[Q[1][f[1]]], k)){ ++j;while (r[0]>f[0] && t[Q[0][r[0]-1]] >= t[j])--r[0];Q[0][r[0]++] = j;while (r[1]>f[1] && t[Q[1][r[1]-1]] <= t[j])--r[1];Q[1][r[1]++] = j;}len = j-i;if (j == n && cmp_ll(t[Q[0][f[0]]], t[Q[1][f[1]]], k)) ++len;if (ans < len) ans = len;if (t[Q[0][f[0]]] == t[j]){while (f[1]<r[1] && !cmp_ll(t[Q[0][f[0]]], t[Q[1][f[1]]], k))++f[1];i = Q[1][f[1]-1]+1;}else if (t[Q[1][f[1]]] == t[j]){while (f[0]<r[0] && !cmp_ll(t[Q[0][f[0]]], t[Q[1][f[1]]], k))++f[0];i = Q[0][f[0]-1]+1;}}printf("%d\n", ans);}return 0; }

?

轉載于:https://www.cnblogs.com/JMDWQ/archive/2012/04/19/2458545.html

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的COJ 1170 A Simple Problem的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。