Я пытаюсь создать код для интернет-судьи 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;
}
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/
Других решений пока нет …