简述:
给定序列, 查询是否存在全部符合给定种类至少给定此种类数量的区间, 并输出最小值
解法:
氵题, 当我知道 T4 是最简单的题但我选择了硬肛 T1 之后:
我在写尺取法
2min later, 我写完尺取法了
几乎是尺取法板子, 即同时移动左右指针, 看是否存在合法序列, 开个桶随便搞搞就行
不会尺取法的可以去康康其他的板子题
- /*cinput
- bool check(int x){
- int l=1,r,cnt=0;
- memset(sum,0,sizeof(sum));
- for(int i=1;i<=x;i++){
- sum[a[i]]++;
- if(sum[a[i]]==q2[a[i]])cnt++;
- }
- if(cnt==k)return 1;
- l=2;
- for(int r=x+1;r<=n;r++,l++){
- if(++sum[a[r]]==q2[a[r]])cnt++;
- if(--sum[a[l-1]]==q2[a[l-1]]-1)cnt--;
- if(cnt==k)return 1;
- }
- return 0;
- }
- int Binary(int l,int r){
- int mid;
- while(l<=r){
- mid=l+r>>1;
- if(check(mid))r=mid-1;
- else l=mid+1;
- }
- return l;
- }
- int main(){
- freopen("drop.in","r",stdin);
- freopen("drop.out","w",stdout);
- int T=read();
- while(T--){
- memset(sum,0,sizeof(sum));
- memset(q2,0,sizeof(q2));
- n=read(),m=read(),k=read();maxx=0;
- for(int i=1;i<=n;i++){
- a[i]=read();sum[a[i]]++;
- }
- int ans;
- for(int i=1;i<=k;i++){
- q1[i]=read(),q2[q1[i]]=read();
- if(sum[q1[i]]<q2[q1[i]]){puts("DESTROY ALL");goto skr;}
- }
- memset(sum,0,sizeof(sum));
- ans=Binary(1,n);
- if(ans==0)puts("DESTROY ALL");
- else printf("%d\n",ans);
- skr:;
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3683644.html