首页 > 代码库 > nyoj133_子序列_离散化_尺取法
nyoj133_子序列_离散化_尺取法
子序列
时间限制：3000 ms | 内存限制：65535 KB
难度：5
- 描述
给定一个序列，请你求出该序列的一个连续的子序列，使原串中出现的所有元素皆在该子序列中出现过至少1次。
如2 8 8 8 1 1，所求子串就是2 8 8 8 1。
- 输入
- 第一行输入一个整数T(0<T<=5)表示测试数据的组数
每组测试数据的第一行是一个整数N(1<=N<=1000000)，表示给定序列的长度。
随后的一行有N个正整数，表示给定的序列中的所有元素。
数据保证输入的整数都不会超出32位整数的范围。 - 输出
- 对于每组输入，输出包含该序列中所有元素的最短子序列的长度
- 样例输入
251 8 8 8 162 8 8 8 1 1
- 样例输出
25
解题思路：刚开始看了网上的解题报告，有个类似的题，可以用stl中的集合set和键值对map来做，结果超时，实践发现每次数据一大，用STL就会超时。
离散化：将a数组的备份temp[]排序，然后把不重复的值都弄到X数组中，接下来开始挨着求出a中的每一个元素在X中的位置，用index记录。
这样每次到a[i]，index[i]中记录的就是a[i]在X[]中的位置。
尺取法：
通过观察发现，所求序列的第一个一定是在序列中只出现1次的，不然就可以直接把这个舍去了。
设置s,e分别为所求序列的起始和结束。
e每次都++，然后当序列中元素个数==非重复元素个数len时，要用minn记录此时序列长度。然后再s++（直到X[index[s]]==1）。
最后到e不小于n然后结束。
代码：
#include<cstdio>#include <iostream>#include<map>#include<set>#include<algorithm>#include <cstring>#define MAXN 1000005using namespace std;int n;int cou;int a[MAXN];//所有元素int X[MAXN];//不重复元素int temp[MAXN];//临时int inde[MAXN];//存储a[]中每一个元素在X中的下标int bin_search(int cou,int aa){ int s=0,e=cou-1; int mid; while(s<=e){ mid=(s+e)>>1; if(X[mid]==aa){ return mid; }else{ if(aa<X[mid]){ e=mid-1; }else{ s=mid+1; } } }}void discrete(){ cou=1; sort(temp,temp+n); X[0]=temp[0]; for(int i=1;i<n;i++){ if(temp[i]!=temp[i-1]){ X[cou++]=temp[i]; } } for(int i=0;i<n;i++){ inde[i]=bin_search(cou,a[i]); }}int main(){ int t; scanf("%d",&t); while(t--){ int minn=1000005; scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%d",&a[i]); temp[i]=a[i]; } discrete(); memset(X,0,sizeof(X)); int len=cou; int s=0,e=0; int number=0; while(e<n){ if(X[inde[e]]==0) number++; X[inde[e]]++; while(X[inde[s]]>=2){ X[inde[s]]--; s++; } if(number==len){ minn=min(minn,e-s+1); /*if(X[inde[s]]==1)*/ number--; X[inde[s]]--; s++; } e++; } printf("%d\n",minn); } return 0;}
nyoj133_子序列_离散化_尺取法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。