프로그램이 너무 오래 실행됩니다. 또한지도가 어떻게 사용되며이 사례와 관련이 있습니까?

Question

나는 uva 온라인 판사의 코드를 작성하려고합니다. 각 테스트 케이스의 첫 번째 행에는 두 개의 정수 n, m (1 < = n; m < = 100 000)이 포함되며, n은 배열의 요소 수이고, m은 쿼리 수입니다. 다음 행에는 1 000 000 이하의 n 양의 정수가 포함됩니다. 다음 m 행에는 두 개의 정수 k와 v가 있습니다 (1 < = k < = n, 1 < = v < = 1 000 000). 각 쿼리에 대해 코드에서 v의 k 번째 항목을 인쇄해야합니다. 번호가 없으면 프로그램은 0을 인쇄해야합니다.

컴파일 할 때마다 완벽하게 작동하지만 프로그램 실행에는 시간이 오래 걸립니다. 필자는 맵을 사용하여 고려했지만 C++에 익숙하지 않았으며 구문을 알지 못했고 실제로 도움이 되는지도 모른다. 누군가 제게 조언 해 줄 수 있나요? 또한 온라인 재판관을 위해 나는 무엇을 입력해야하는지 사용자에게 말하지 않습니다. 가능한 한 표준 라이브러리를 사용하고 싶습니다.

#include<iostream> 
#include<vector> 
#include<string> 



using namespace std; 
int main() 
{ 


    long n,m,k,v,count=0;     //initialise evrything 
    cin>>n>>m; 
    vector<long>N(n); 
    if(n==0) 
    { 
     for(long p=0;p<m;p++)    //special case if n is 0 
     { 
      cin>>k>>v; 
      cout<<"0"<<endl; 

     } 

    } 
    else 
    { 

     for(long i=0;i<=n-1;i++)    //give vector values 

     { 
      cin>>N[i];      //user inputs n values into N 


     } 

     for(long j=0;j<m;j++) 
     { 
      cin>>k>>v;     //input k and v 
      for(long y=0;y<=n;y++) 
      { 
       if (N[y]==v && y<n)  
       { 
        count=count+1;   // count instances of v 
        if (count==k)   // end loop if kth position of v 
              // is found 
        { 
         cout<<y+1<<endl; 
         break; 

        } 
        else if(y==n)   //if end of array reached print 0 
        { 
         cout<<"0"<<endl; 

        } 
       } 
       else if(y==n)    //if end of array reached print 0 
       {cout<<"0"<<endl;} 


      } 


      count=0;        //reset count 

     } 




    } 
    return 0; 
} 

Answer 1

지도는 여기에서 사용할 수있는 최상의 STL 컨테이너가 아닙니다.이 경우에는 멀티 세트가 더 좋습니다. 지도는 X가 언급 된 커플 (X, Y)이있을 때 유용합니다. 세트는 동일한 것이지만 커플이 없지만 X로 참조되는 값 (X)이 하나뿐입니다. 따라서이 경우 Set은 Map보다 유용합니다. 그러면 여러 개의 동일한 값을 가질 수 있으므로 Multiset이 선택됩니다.

myMultiset.emplace(i); 추가 값 '내가'는 MULTISET

더 설명서의 MULTISET에 'V'의

myMultiset.count(v); 반환 번호 : http://www.cplusplus.com/reference/set/multiset/