注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

东月之神

在单纯的观念里面,生命就容易变得比较深刻!

 
 
 

日志

 
 
关于我

别驻足,梦想要不停追逐,别认输,熬过黑暗才有日出,要记住,成功就在下一步,路很苦,汗水是最美的书!

网易考拉推荐

xmu 1213.卡片  

2011-12-08 21:43:05|  分类: ACM |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
1213.卡片
Time Limit: 2000 MS         Memory Limit: 65536 K
Total Submissions: 224 (57 users)         Accepted: 52 (29 users)
[ My Solution ]

Description

有N张卡片排成一排(标记从1到N),每张卡片都有一个由小写字母构成的名字。这N张卡片有些可能含有相同的名字,它们被看作是相同种类的卡片。问这N张卡片中能够包含所有种类的卡片的最小区间是多少?

Input

第一行输入一个整数N(1<=N<=100,000)。
接下来按卡片的标记顺序输入N行,表示卡片的名字,每个名字不超过20个字母。

Output

输出一个数,表示包含所有种类卡片的最小区间。

Sample Input

7
barcelona
barcelona
intermilan
barcelona
bayern
bayern
intermilan

Sample Output

3

Source
 
a的如此辛苦,一开始一直由于前面的判断相同的卡片而不知道用什么方法,用了字符串hash总是WA。直接比较又老师TLE。没办法了,想到了还有STL中强大的map。最后终于A掉了。。。。。。。。RT。。。。。。。。。。
#include <stdio.h>          
#include <string.h>          
#include <map>
#include <string>
#include <iostream>
using namespace std;
     
struct card          
{          
     char name[21];          
     int num;          
}a[100005]; 
                   
int main()          
{             
   int hash[100005];        
   int n, cnt;          
   scanf("%d", &n);         
   cnt = 1;    
   map<string, int> map1;              
   for(int i = 0; i < n; i++)          
   {          
       scanf("%s", a[i].name);     
       hash[i] = 0;
    if(i == 0)
    { 
      map1.insert(pair<string, int>(a[i].name, 0));
      a[i].num = 1;
    } 
       int aa =  map1[a[i].name];
       if(aa == 0)
       {
    map1[a[i].name] = cnt;
    a[i].num = cnt;
    cnt++;
       }
        else
      a[i].num = aa;              
   } 
   cnt--;         
   int maxn =  100005;                     
   int i = 0, j, ans = 0;          
   for(j = 0; j < n; j++)          
   {          
       if(hash[a[j].num] == 0)          
       {          
           hash[a[j].num] = 1;          
           ++ans;          
           if(ans == cnt)          
           {                                       
               for(; i <= n-cnt; i++)          
               {          
                   if(hash[a[i].num] == 1)          
                   {          
                       hash[a[i].num] = 0;          
                       --ans;        
                       i++;         
                       break;          
                   }          
                   else  if(hash[a[i].num] > 1)       
                       hash[a[i].num]--;          
               }        
               if(maxn > (j-i+2))          
                   maxn = j-i+2;                           
           }          
       }          
       else    hash[a[j].num]++;          
   }          
   printf("%d\n", maxn);            
return 0;          

  评论这张
 
阅读(101)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017