Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

为什么要deque?我直接que,好心人可以站内信

Posted by lqp18_31 at 2009-08-04 10:23:51 on Problem 3320 and last updated at 2009-08-04 10:25:03
rt
而且手写队列和map和读入居然很慢……300+ms
向来手写读入是相当快的啊……

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctype.h>
#include<algorithm>
#include<queue>
#include<vector>
#include<bitset>
using namespace std;
FILE *fin=freopen( "3320.in" , "r" , stdin );
FILE *fout=freopen( "3320.out" , "w" , stdout );
int N,a[ 1010000 ];
int g[ 1000003 ],dat[ 1010000 ],next[ 1010000 ],size; 
int cnt[ 1000003 ];
struct queue{
       int head,tail;
       int a[ 1010000 ];
       int size(){
           return head-tail;
       }
       void push( int m ){
            a[ ++head ]=m;
       }
       int front() { return a[ tail+1 ]; }
       void pop() { tail++; }
}Q;

int getint()
{
     int ret=0; char tmp; 
     while( !isdigit( tmp=getc( fin ) ) );
     do{
            ret=( ret<<3 )+( ret<<1 )+tmp-'0';
     }while( isdigit( tmp=getc( fin ) ) );
     return ret;
}

int find( int m )
{
    int h=m%1000003;
    int p=g[ h ];
    while( p ){
           if( dat[ p ]==m ) return p;
           p=next[ p ];
    }
    next[ ++size ]=g[ h ];
    g[ h ]=size;
    dat[ size ]=m;
    return size;
}

int main()
{
    N=getint();
    for( int i=1 ; i<= N ; i++) a[ i ]=find( getint() );
    
    int j=1,tot=0,ans;
    while( tot<size ){
           if( cnt[ a[ j ] ]==0 ) tot++;
           cnt[ a[ j ] ]++;
           Q.push( a[ j++ ] );
           while( cnt[ Q.front() ]>1 ) --cnt[ Q.front() ],Q.pop();
    }
    ans=Q.size();
    while( j<=N ){
           cnt[ a[ j ] ]++;
           Q.push( a[ j ] );
           while( cnt[ Q.front() ]>1 ) --cnt[ Q.front() ],Q.pop();
           ans=min( ans , Q.size() );
           j++;
    }
    cout << ans << endl;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator