[luoguP2564] [SCOI2009]生日礼物（队列）

传送门

不停的枚举 l ，然后枚举长度，直到所有颜色都包含，这是 n² 做法，超时。

仔细想想，可以用个队列来维护。

还是枚举 l ，用队列来维护当前区间的包含所有颜色，l 增加时再判断。

——代码

1 # include <iostream> 2 # include <cstdio> 3 # include <cstring> 4 # include <string> 5 # include <cmath> 6 # include <vector> 7 # include <map> 8 # include <queue> 9 # include <cstdlib> 10 # include <algorithm> 11 # define MAXN 1000001 12 using namespace std; 13 14 inline int get_num() 21 22 int n, k, tot, sum, h, t, ans = 1 << 30; 23 int num[MAXN]; 24 25 struct node 26 p[MAXN]; 29 30 inline bool cmp(node x, node y) 31 34 35 int main() 36 51 if(sum == k) ans = min(ans, p[t].pos p[h].pos); 52 num[p[h].a]; 53 if(!num[p[h].a]) sum; 54 } 55 printf("%d", ans); 56 return 0; 57 }
View Code

上一篇：[HDU2196]Computer（DP）

下一篇：[Tyvj1939] 玉蟾宫（单调栈）

---

单调队列