[数据结构与算法]逛画展（单调队列） acm寒假集训日记22/1/1

题目如下：

?

AC代码如下：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<list>
#define inf 99999999
/*其实O(n)就能做。
对于一个数，我们维护它最后出现的位置p [ ] 。那么对于L~R（假设已经达到m种画都有），
R+1时，至少一个数的p会被更新。那么如果这个左端点在这个区间中还有一个，即 L < p [ a [ L ] ] ，
那么这个L删掉是没有影响的，我们就让L++；否则L不变，这样保证这个队伍里必定1~m都有，更新答案即可。*/
using namespace std;
const int MAX = 1e6+9;
int p[MAX];
int a[MAX];
int L = 0,R = inf;
int main()
{
	int n,k;
	scanf("%d %d",&n,&k);
	for(int i = 1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	int l = 1;
	int cnt = 0;
	for(int i = 1;i<=n;i++)
	{
		if(!p[a[i]])
		cnt++;
		p[a[i]] = i;
		while(l<p[a[l]])
		l++;
		if(cnt==k&&R-L+1>i-l+1)
		{
			L = l;
			R = i;
		}
	}
	cout<<L<<' '<<R; 
}

代码解析：

典型单调队列（模板题）

最优：

1：1~m都出现过。

2：长度最短。

开一个计算器cnt来记录1~m出现了几个

if(!p[a[i]])
cnt++;

每次进队列我们就可以更新r (r = i)

那我们如何更新l呢？

while(l<p[a[l]])
l++;

当满足这个条件时，相当于 当前进队列的 不会对 原状态产生影响，那l++。

举个例子：【1 2 3 4】1 下一个状态——》1【2 3 4 1】

当cnt == m时，已满足最优条件1，我们比较上一次的长度（初始长度定义为 无穷大）得到最小长度，反复比较最终满足最优条件2——》得到答案！

?

最后发个牢骚：动态规划（单调栈 /队列）有点难（www）,今天研究了一天，感觉还是不太行 www

所以我要继续努力，披荆斩棘，再硬也把他吃透（哈哈哈！！！）

最后的最后：祝大家 元旦快乐！！！