Диапазон запроса для массива - PullRequest
Новая
       33

Диапазон запроса для массива

0 голосов
/ 22 апреля 2020

Этот вопрос из заданий на кодирование кажется легким. Я решил это, используя свой подход, заботясь обо всех условиях. Но мой код работает только для 1 контрольного примера из 55 контрольных примеров, для остальных из них превышено ограничение по времени. Я до сих пор не понимаю, как оптимизировать мой код. Пожалуйста, помогите мне с правильным решением.

Проблема состоит в следующем: вам даны два массива, массив A размера n и массив B размера m. Массив A будет иметь целые числа от 1 до m, а в массиве B ожидаемое вхождение каждого числа, присутствующего в массиве A. Теперь у вас есть запросы в форме диапазона, и если для данного диапазона, вхождение каждого числа в этом диапазоне массива A равно к его ожидаемому вхождению, присутствующему в массиве B, тогда вы должны вывести 1, иначе 0.

Мой код: 

 #include<bits/stdc++.h>
 using namespace std;
 #define ll long long int 
 int main() 
 {
ios_base::sync_with_stdio(false);

cin.tie(NULL);
ll n, m, i;
cin >> n >> m;
ll arr[n],a;
//long long int arr1[m] = { 0 };

for (i = 0; i < n; i++) {
    cin >> arr[i];
}

for (i = 0; i < m; i++) {
    cin >> a;
}

ll q, j;
cin >> q;
ll arr2[q][2];

for (i = 0; i < q; i++) {
    for (j = 0; j < 2; j++) {
        cin >> arr2[i][j];
    }
}

for (ll i = 0; i < q; i++) {
    ll start = arr2[i][0];
    ll end = arr2[i][1];

    unordered_map<ll, ll> freq;
    for (ll i = start - 1; i < end; i++) {
        freq[arr[i]]++;
    }

    ll cnt = 0;
    for (auto x : freq) {
        if (x.first != x.second) {
            cnt++;
            break;
        }
    }
    if (cnt != 0) {
        cout << "0" << '\n';
    } else {
        cout << "1" << '\n';
    }

}

}

Как пройти все тестовые случаи, не превышая TIME LIMIT EXCEEDED?

Ответы [ 2 ]

0 голосов
/ 24 апреля 2020

Если я правильно понимаю ...

Псевдокод: 

int n <<     // number of values going into nn
int nn[n] << // values to check
int m <<     // number of frequencies (range of values) going into mm
int mm[m] << // expected frequencies
int low <<   // low value to check from
int high <<  // high value to check to

for (int i = 0; i < n; i++)
  mm[nn[i]-1]--; // -1 because values are 1 though m, not 0 though m-1

int good = 1; // assume success

for (int i = low+1; i <= high+1; i++)
  if (mm[i] != 0)
  {
    good = 0;
    break;
  }

good >>
0 голосов
/ 23 апреля 2020

В вашем вопросе есть некоторая двусмысленность, так как в заявлении о проблеме говорится, что есть массив B, в котором ожидаемое вхождение каждого элемента, но в вашем коде вы, кажется, просто сопоставляете значение каждого элемента с его вхождением. В любом случае, алгоритм, описанный в этой статье , даст вам ответ.

Основная идея заключается в том, что вы должны сначала отсортировать запросы, чтобы вам не приходилось считать частоту элементы во всем диапазоне для каждого запроса (что приводит к сложности O(m*n) для вашей текущей реализации). Алгоритм, описанный в статье, подсчитывает количество элементов, соответствующих требуемой частоте в диапазоне для каждого запроса (переменная currentAns). Вам просто нужно сопоставить currentAns с количеством элементов на карте (freq), чтобы вывести 0 / 1.

РЕДАКТИРОВАТЬ:

Это может быть оптимизировано в дальнейшем. Вы можете избавиться от карты ha sh и сохранить частоты в массиве размером m. Сохраняйте количество элементов, соответствующих ожидаемой частоте, используя те же логики c, что и в ответе выше (currentAns). Дополнительно следите за количеством различных элементов в диапазоне, используя другую переменную (скажем, distinctElements), используя те же логики обновления c (обновление, когда частота больше 1). Выведите 1, если distinctElements==currentAns, 0 в противном случае. Это снизит общую сложность до O(n*sqrt(n)). В этом блоге приведено отличное объяснение алгоритма MO, а также пример кода для получения различных элементов в диапазоне.

...