Моя программа работает слишком долго. Кроме того, как используются карты и имеют ли они отношение к этому делу?

Я пытаюсь создать код для интернет-судьи uva. Первая строка каждого теста содержит два целых числа n, m (1 <= n; м <= 100 000), где n — количество элементов в массиве, а m — количество запросов. Следующая строка содержит n натуральных чисел, не превышающих 1 000 000. Каждая из следующих m строк содержит два целых числа k и v (1 <= к <= n, 1 <= v <= 1 000 000). для каждого запроса код должен вывести k-й случай v. если такого числа не существует, программа должна вывести 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;
}

-4

Решение

Map — не лучший STL-контейнер для использования здесь: мультисеть лучше в этом случае.
Обратите внимание, что Map полезна, когда у вас есть пары (X, Y), которые называются X. Set — это то же самое, но без пары, а только одно значение (X), на которое ссылается X. Так что в этом случае Set более полезен чем карта.
Затем выбирается Multiset, потому что они могут содержать несколько одинаковых значений.
Итак, здесь есть две функции:

myMultiset.emplace(i); Добавьте значение ‘i’ к мультимножеству

myMultiset.count(v); Возвращает номер ‘v’ в мультимножестве

Больше документации: http://www.cplusplus.com/reference/set/multiset/

0

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]