首页 > 代码库 > 51nod1127(尺取法)

51nod1127(尺取法)

题目链接:https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1127

 

题意:中文题诶~

 

思路:尺取法

维护一个队列,若当前队首的元素在后面出现了,那么我们就将其删除,若当前队列里含有26个字母,我们就记录其size。

取所有size里面的最小值就是我们要的答案。。。

 

代码:

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string>
 4 #include <queue>
 5 #include <string.h>
 6 #define MAXNV 30
 7 #define MAXNA 100010
 8 using namespace std;
 9 
10 int vis[MAXNV];
11 char a[MAXNA];
12 
13 int main(void){
14     int value=http://www.mamicode.com/0, ans=MAXNA;
15     queue<char> q;
16     scanf("%s", a);
17     int len=strlen(a);
18     for(int i=0; i<len; i++){
19         q.push(a[i]);
20         if(!vis[a[i]-A]){
21             value++;
22         }
23         vis[a[i]-A]++;
24         while(vis[q.front()-A]>=2){
25             vis[q.front()-A]--;
26             q.pop();
27         }
28         if(value>=26){
29             int gg=q.size();
30             ans=min(ans, gg);
31         }
32     }
33     if(value<26){
34         cout << "No Solution" << endl;
35     }else{
36         cout << ans << endl;
37     }
38     return 0;
39 }

 

51nod1127(尺取法)