题目描述
dd_engi同学最爱的食物就是面包啦！dd_engi要去参加RQNOJ一周年邀请赛，为了在参加比赛的时候能吃面包，这一天他又来到了面包店长长的货架前。面包店的货架上按次序放了N个面包，每个面包用一个数字表示它的种类。所有种类的面包dd都很喜欢，而且，贪心的他，希望每种面包都能至少吃到K个。为了吃起来方便，dd打算从面包的序列中选择连续的一段来吃掉。现在的问题是，在满足要求的前提下，如果希望吃掉的面包最少，dd_engi应该怎样选择呢？
样例说明
一共有13个面包，从第二行的序列可以看出有三个不同的种类“1”、“2”和“3”。要求是这三种面包每种都要吃掉至少两个。最优的方案是吃掉从第1个到第7个这七个面包，也就是选择“1 2 3 3 3 1 2”这一段序列。从第5个面包开始的序列“3 1 2 3 2 2 1”也满足要求，但应该输出最靠前的那个，也就是“1 7”。
数据规模
对于20%的数据，N<=20。
对于40%的数据，N<=1024。
对于100%的数据，1<=N<=1000000，1<=K<=N，其它整数在[0,1e9]的范围内。
[出题:dd_engi]
[题目版权:未经RQNOJ许可，不允许以任何方式转载本题]
[对于FP的选手,5-10测试点时限为3.5s,C++可以在1s内出解]
输入格式
第一行，空格隔开的两个整数N和K。
第二行有N个整数，表示货架上按次序的N个面包所属的种类，相同的整数表示相同的种类。
输出格式
需要输出两个整数，表示dd选择吃掉的面包序列的起始和终止位置。如果有多个答案满足要求，输出起始位置最靠前的。对于无解的数据，输出-1。
dd_engi出的题就是难啊！时间复杂度O(n)啊！
既要hash，又要一些打死我都想不到的方法解题。
唉，学无止境啊。
1 #include<iostream> 2 #define X 9999997 3 //#include<fstream> 4 using namespace std; 5 //ifstream fin("cin.in"); 6 7 int n,m,e[1000010],q[X]; 8 int hash[X],tot=0; 9 bool vis[X]; 10 11 void Hash(){ 12 int x,y; 13 for(int i=1;i<=n;++i) 14 { 15 scanf("%d",&x); 16 y=x%X; 17 while(hash[y]!=0&&hash[y]!=x) y++; 18 if(hash[y]==0) {hash[y]=x;tot++;} 19 e[i]=y; 20 } 21 } 22 23 int main() 24 { 25 int i,j; 26 cin>>n>>m; 27 28 Hash(); 29 30 j=1; 31 int sum=0,ans1,ans2,min=100000000; 32 for(i=1;i<=n;++i) 33 if(sum<tot) 34 { 35 q[e[i]]++; 36 if(q[e[i]]>=m&&!vis[e[i]]) 37 {sum++;vis[e[i]]=1;} 38 39 if(sum==tot) 40 { 41 while(j<=i&&q[e[j]]>m) {q[e[j]]--;j++;} 42 if(i-j<min) {min=i-j;ans1=j;ans2=i;} 43 } 44 } 45 else 46 { 47 q[e[i]]++; 48 while(j<=i&&q[e[j]]>m) {q[e[j]]--;j++;} 49 if(i-j<min) {min=i-j;ans1=j;ans2=i;} 50 } 51 if(min==100000000) {cout<<-1<<endl;return 0;} 52 cout<<ans1<<" "<<ans2<<endl; 53 // system("pause"); 54 return 0; 55 56 }