博览馆正在展出由世上最佳的M位画家所画的图画。人们想到博览馆去看这几位大师的作品。可是,那里的博览馆有一个很奇怪的规定,就是在购买门票时必须说明两个数字,a和b,代表要看展览中的第a幅至第b幅画(包含a和b)之间的所有图画,而门票的价钱就是一张图画一元。人们希望入场后可以看到所有名师的图画(至少各一张)。可是又想节省金钱……请你写一个程序决定购买门票时的a值和b值。
第一行是N和M,分别代表博览馆内的图画总数及这些图画是由多少位名师的画所绘画的。
其后的一行包含N个数字,它们都介于1和M之间,代表该位名师的编号。
a和b(a≤b)由一个空格符所隔开。
保证有解,如果多解,输出a最小的。
12 5 2 5 3 1 3 2 4 1 1 5 4 3
2 7
N≤1000000, M≤2000。
#include<bits/stdc++.h>
using namespace std;
const int maxN=1e3+10;
struct Node{
int l,r,mon;
}a[1000010];//每个考虑方案的左右边界和花费
queue<int>q;
int d[maxN];
int n,m,ans,money,k,tot=1;
bool cmp(Node,Node);
int main(){
cin>>n>>m;
for (int i=1;i<=n;i++){
int x;
cin>>x;
q.push(x);//读入
if (ans<m){
if (!d[x]) ans++;
d[x]++;
money++;
k=i;
}//(第一种方案)如果还有画师的画没看,就压入队列
}
for (int i=1;i<=n;i++){
while (d[q.front()]>1){
money--;
q.pop();
i++;
}//优化上个方案,左边界移动
a[tot++]={i,k,money};//进入结构体
d[q.front()]--;
q.pop();
i++;//左边界移动
while (!d[q.front()]){
money++;
k++;
}//继续加,更改右边界
a[tot++]={i,k,money};//进入结构体
}
sort(a+1,a+n+1,cmp);//排序
cout<<a[1].l<<' '<<a[1].r<<endl;//输出
return 0;
}
inline bool cmp(Node a,Node b){
if (a.mon!=b.mon) return a.mon<b.mon;
return a.l<b.l;
}//比较函数