| Time Limit: 12000MS | Memory Limit: 65536K | |
| Total Submissions: 73426 | Accepted: 20849 | |
| Case Time Limit: 5000MS | ||
Description
| Window position | Minimum value | Maximum value |
|---|---|---|
| [1 3 -1] -3 5 3 6 7 | -1 | 3 |
| 1 [3 -1 -3] 5 3 6 7 | -3 | 3 |
| 1 3 [-1 -3 5] 3 6 7 | -3 | 5 |
| 1 3 -1 [-3 5 3] 6 7 | -3 | 5 |
| 1 3 -1 -3 [5 3 6] 7 | 3 | 6 |
| 1 3 -1 -3 5 [3 6 7] | 3 | 7 |
Your task is to determine the maximum and minimum values in the sliding window at each position.
Input
Output
Sample Input
8 31 3 -1 -3 5 3 6 7
Sample Output
-1 -3 -3 -3 3 33 3 5 5 6 7
题目大意：
给你长度为n的数列，要你输出1..k, 2..k+1, 3..k+2, ...区间的最大值和最小值。
单调队列经典题。
维护单调不减序列和单调不增序列的下标，这样队首就分别是最小值和最大值的下标。
以单调不减序列举例：
每次向后移动，先删除队尾元素直至小于等于新元素。贪心的思想，之前队尾元素如果比它大，那该队尾元素永远不可能成为某个区间的最小值。
再判断队首元素是否在k区间内。
单调不增序列同理。
单调队列可以用deque写。
对这两个队列考虑，（平摊分析）每个元素最多入队出队两次。复杂度O(n)。
所以TLE总是让人觉得僵硬。On, 1e6, T???
其实是io太慢了。
scanf printf 相对cin cout 来说确实快了，但这个可是1e6+2e6啊 。。￣へ￣
第一次真正明白输入输出挂的含义。
scanf printf 其实就是对putchar getchar 等函数的封装，功能强大但臃肿。所以，要用一些速度比scanf快，但功能比putchar全面的函数取而代之。
输入输出挂（正负整数）。
templateinline bool scan_d(T &ret){ char c; int sgn; if (c = getchar(), c == EOF) { return 0; //EOF } while (c != '-' && (c < '0' || c > '9')) { c = getchar(); } sgn = (c == '-') ? -1 : 1; ret = (c == '-') ? 0 : (c - '0'); while (c = getchar(), c >= '0' && c <= '9') { ret = ret * 10 + (c - '0'); } ret *= sgn; return 1;}template inline void print_d(T x){ if(x < 0) { putchar('-'); x = -x; } if (x > 9) { print_d(x / 10); } putchar(x % 10 + '0');}
由上面的代码可以看出，输出一个整数的复杂度并不是o1的，取决于输出数的位数，是o(m)，m是常数。如果数是int，n又很大（1e6），复杂度其实是o(mn)，用printf的话可以当成onlogn+算了，t也不奇怪吧。
不过该挂对C++极度无感（不知道为啥。。），对G++就很真实了。从下图来说，scanf用c++会快一点，不过真遇到大量输出，g++&挂是最佳选择，所以忘了c++吧。
AC代码：
#include#include #include #include #include #include #include #include typedef long long ll;const int maxn=1000000;template inline bool scan_d(T &ret){ char c; int sgn; if (c = getchar(), c == EOF) { return 0; //EOF } while (c != '-' && (c < '0' || c > '9')) { c = getchar(); } sgn = (c == '-') ? -1 : 1; ret = (c == '-') ? 0 : (c - '0'); while (c = getchar(), c >= '0' && c <= '9') { ret = ret * 10 + (c - '0'); } ret *= sgn; return 1;}template inline void print_d(T x){ if(x < 0) { putchar('-'); x = -x; } if (x > 9) { print_d(x / 10); } putchar(x % 10 + '0');}int arr[maxn+5];int temp[maxn+5];int ans[maxn][2];int cmp(int x,int y){ return arr[x]