题解 P1638 【逛画展】

类似滑动窗口的贪心。 考虑暴力。枚举右端点，贪心找到一个**最优的**左端点，判断区间长度是否更优，更新答案。 尝试将这个暴力优化。 考虑右端点从1开始一步一步往右边推。我们增加一个数组pos记录大师最晚出现的位置。显然每次右端点往右移一位，就会有一个大师的pos被更新。 若左端点在上一个右端点的最优解为l，我们考虑左端点上的画是k。若l<pos[k]，是不是这个画根本就没有必要看下去了？因为这个画在后面能够看到，而这个画又处于最左边，可以选择不看，于是此时我们应该把l往右移一位，显然这是符合贪心策略的。但若l==pos[k]，l显然不能右移，因为这样不符合**包含所有种类的画**的条件。 于是我们便可以在每次右端点向右移一位，再贪心地更新左端点的位置来找到左端点的最优解，这就是一个优化的暴力。然后每次就判断区间长度是否更优就行了。 **一些细节：** 首先这个区间里面必须包含所有的画。一开始把pos初始化为-1，则如果左端点的画仅出现过一次，那么左端点不会更新。当所有的pos都不为-1的时候，才可以统计答案。 嘛，很像滑动窗口。 细节见代码： ```cpp #include<bits/stdc++.h> using namespace std; const int N=1e6+10,M=2e3+10; int mlen=0x7fffffff,ml,mr; // 记录答案 int pos[M]; // 记录种类画最后一次出现的位置 int pic[N],l=1,cnt; // 画、左端点和已经包含了多少种类的画 int main(){ ios::sync_with_stdio(false); int n,m; cin>>n>>m; int na; memset(pos,-1,sizeof(pos)); for(int i=1;i<=n;i++){ cin>>pic[i]; if(pos[pic[i]]==-1) cnt++; // 如果没有出现，统计+1 pos[pic[i]]=i; // 更新位置 while(l!=i && l<pos[pic[l]]) l++; // 更新左端点 if(cnt==m && i-l+1<mlen) mlen=i-l+1,ml=l,mr=i; // 如果已经包含了所有种类的画，而且区间较之前更小，更新答案 } cout<<ml<<' '<<mr<<endl; return 0; } ```