题解 P1638 【逛画展】

Sino_E · 2017-11-09 17:49:06 · 题解

类似滑动窗口的贪心。

考虑暴力。枚举右端点，贪心找到一个最优的左端点，判断区间长度是否更优，更新答案。

尝试将这个暴力优化。

考虑右端点从1开始一步一步往右边推。我们增加一个数组pos记录大师最晚出现的位置。显然每次右端点往右移一位，就会有一个大师的pos被更新。

若左端点在上一个右端点的最优解为l，我们考虑左端点上的画是k。若l<pos[k]，是不是这个画根本就没有必要看下去了？因为这个画在后面能够看到，而这个画又处于最左边，可以选择不看，于是此时我们应该把l往右移一位，显然这是符合贪心策略的。但若l==pos[k]，l显然不能右移，因为这样不符合包含所有种类的画的条件。

于是我们便可以在每次右端点向右移一位，再贪心地更新左端点的位置来找到左端点的最优解，这就是一个优化的暴力。然后每次就判断区间长度是否更优就行了。

一些细节： 首先这个区间里面必须包含所有的画。一开始把pos初始化为-1，则如果左端点的画仅出现过一次，那么左端点不会更新。当所有的pos都不为-1的时候，才可以统计答案。

嘛，很像滑动窗口。

细节见代码：

#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;
}