题目链接:zjbti1110
【题意】一个含有n项的数列(1<=n<=2000000),求出每一项前的m个数到它这个区间内(本身不算)的最小值。若前面的数不足m项则从第1个数开始,若前面没有数则输出0。
【分析】这道题目,我们很容易想到线段树、或者st 算法之类的 RMQ 问题的解法。但庞大的数据范围让这些对数级的算法没有生存的空间。我们先尝试用动态规划的方法。用f[i]代表第i个数对应的答案,a[i]表示第i个数,很容易写出状态转移方 程:
这个方程,直接求解的复杂度是 O(nm)的,甚至比线段树还差。这时候,单调队列就发挥了他的作用:
我们维护这样一个队列:队列中的每个元素有两个域{position,value},分别
代表他在原队列中的位置和a[i],我们随时保持这个队列中的元素两个域都单调递增。
那计算f[i]的时候,只要在队首不断删除,直到队首的 position 大于等于
i-m+1,那此时队首的 value 必定是f[i]的不二人选,因为队列是单调的!
我们看看怎样将a[i]插入到队列中供别人决策:首先,要保证 position 单调 递增,由于我们动态规划的过程总是由小到大(反之亦然),所以肯定在队尾插入。又因为要保证队列的 value 单调递增,所以将队尾元素不断删除,直到队尾元素小于a[i]。
【时间效率分析】 很明显的一点,由于每个元素最多出队一次、进队一次,所以时间复杂度是O(n)。用单调队列完美的解决了这一题。
【AC CODE】1060ms
#include <cstdio> #include <cstring> #include <cctype> #include <cmath> #include <map> //#include <unordered_map> #include <queue> #include <stack> #include <vector> #include <string> #include <algorithm> using namespace std; typedef long long LL; #define rep(i,a,n) for(int i = a; i < n; i++) #define repe(i,a,n) for(int i = a; i <= n; i++) #define per(i,n,a) for(int i = n; i >= a; i--) #define clc(a,b) memset(a,b,sizeof(a)) const int INF = 0x3f3f3f3f, MAXN = 2000000+10; struct NODE{ int id,val; NODE(int a = 0, int b = 0){ id = a, val = b; } }; deque<NODE> q; int a[MAXN]; int main() { #ifdef SHY freopen("e:\\1.txt", "r", stdin); #endif int t; scanf("%d%*c", &t); while(t--) { int n,m; scanf("%d %d%*c", &n, &m); rep(i,0,n) scanf("%d%*c", &a[i]); q.clear(); puts("0"); rep(i,0,n-1) { //队尾加入a[i],删除>=a[i]的数 if(q.empty()) q.push_back(NODE(i,a[i])); else { while(!q.empty() && a[i] < q[q.size()-1].val) q.pop_back(); q.push_back(NODE(i,a[i])); } //更新dp[i]为队首id>i-m的值 while(q[0].id < i-m+1) q.pop_front(); printf("%d\n", q[0].val); } } return 0; }