题意:n个数的序列,长为k个数的窗口,窗口从左从右移,问窗口移动过程中每个状态的最小最大值。
题目链接:http://poj.org/problem?id=2823
——>>单调队列练手。。
C++用时5391MS,G++会TLE。。不解。。望路过的朋友指导一下原因。。
#include <cstdio> #include <vector> #include <queue> const int MAXN = 1000000 + 1; int arrIn[MAXN]; int arrRet[MAXN]; int arrDq[MAXN]; int arrId[MAXN]; void Pop(const int& nVal, const bool& bFlag, const int& nFront, int& nTail) { if (!bFlag) { while (nFront != nTail && nVal <= arrDq[nTail - 1]) { nTail--; } } else { while (nFront != nTail && nVal >= arrDq[nTail - 1]) { nTail--; } } } void GetRet(int n, int k, bool bFlag = false) { int nFront = 0; int nTail = 0; for (int i = 0; i < n; ++i) { Pop(arrIn[i], bFlag, nFront, nTail); arrDq[nTail++] = arrIn[i]; arrId[nTail - 1] = i; while (nFront != nTail && arrId[nFront] <= i - k) { nFront++; } if (i >= k - 1) { arrRet[i - k + 1] = arrDq[nFront]; } } } void Read(int n) { getchar(); for (int i = 0; i < n; ++i) { scanf("%d", arrIn + i); } } void Output(int* arr, int n) { for (int i = 0; i < n - 1; ++i) { printf("%d ", arr[i]); } if (n) { printf("%d\n", arr[n - 1]); } } int main() { int n, k; while (scanf("%d%d", &n, &k) == 2) { Read(n); GetRet(n, k); Output(arrRet, n - k + 1); GetRet(n, k, true); Output(arrRet, n - k + 1); } return 0; }