首页 > 代码库 > hdu 2158 不错的想法题
hdu 2158 不错的想法题
思路 :
两个变量i j 对每一个i满足查找的都用j来维护 是的这个区间的长度是对i的最小满足要求的区间 这样就不用跑O^n的时间复杂度了
#include<stdio.h> #include<string.h> #include<iostream> using namespace std; int num[100010],mark[100010]; int main() { int n,m,Q,i,j; while(~scanf("%d%d",&n,&m)) { if(n==0&&m==0) break; for(i=1;i<=n;i++) scanf("%d",&num[i]); while(m--) { scanf("%d",&Q); memset(mark,0,sizeof(mark)); int a; int cont=0; for(i=1;i<=Q;i++) { scanf("%d",&a); if(mark[a]==0) cont++; mark[a]=1; } int leap[100010]; memset(leap,0,sizeof(leap)); int Min; int flash=0; for(i=1;;i++) { if(mark[num[i]]==0) continue; for(j=i;j<=n;j++) { if(mark[num[j]]) { if(leap[num[j]]==0) flash++; leap[num[j]]++; } if(flash==cont) break; } break; } Min=j-i+1; leap[num[i]]--; if(leap[num[i]]==0) flash--; for(i++;i<=n;i++) { if(!mark[num[i]]) continue; if(flash==cont) { if(j-i+1<Min) Min=j-i+1; leap[num[i]]--; if(leap[num[i]]==0) flash--; continue; } for(j++;j<=n;j++) { if(!mark[num[j]]) continue; if(leap[num[j]]==0) flash++; leap[num[j]]++; if(flash==cont) break; } if(flash==cont&&j-i+1<Min) Min=j-i+1; leap[num[i]]--; if(leap[num[i]]==0) flash--; } printf("%d\n",Min); } } return 0; }
hdu 2158 不错的想法题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。