Блог

Я создаю код для решения проблемы в Исландии.Kattis.Com называется voff, в котором вы должны рассчитать количество собак, необходимое для создания определенной частоты лая.

Существует N лаев, и каждая собака может лаять до одного раза каждые K секунд. Первая строка ввода содержит N и K, вторая строка содержит время, в которое был слышен лай.

Я создал код на Python, который почти достаточно быстр, чтобы получить 100 баллов, но немного стесняется этого. Поэтому я решил написать тот же код, но на C (clang 7.0.0-3 ~ ubuntu0.18.04.1), и когда я запускаю любой другой тестовый пример, кроме первого, я получаю превышение лимита памяти.

Я пытался использовать ‘long long’, ‘unsigned long long’ и ‘int’, но у меня превышен лимит памяти для всех из них.

 #include <bits/stdc  .h>
using namespace std;


int main() {
  int N, K;
  vector<int> barks;
  vector<int> dogs;
  dogs.push_back(0);

  cin >> N >> K;
  for(int i = 0; i < N; i  ){
    int inp;
    cin >> inp;
    barks.push_back(inp);
  }


  for(int bark : barks){
    for(int i = 0; i < dogs.size(); i  ){
      if (bark >= dogs[i]){
        dogs[i] = bark   K;
        break;
      } else {
        dogs.push_back(bark   K);
      }
    }
  }
  cout << dogs.size() << endl;
}
  

При вводе первого тестового примера вывод является и должен быть ‘1’.
Но при запуске любого другого тестового примера он превышает лимит памяти.

В итоге вы получаете бесконечное количество собак, поскольку каждая собака, которую вы добавляете в for i цикл, не проходит bark >= dogs[i] тест, что приводит к добавлению другой собаки и так далее.

Изменение вашего кода, чтобы добавить только одну строку, когда ни одна строка не соответствует условию, работает:

 for (int bark : barks) {
    bool found = false;
    for (int i = 0; i < dogs.size(); i  ) {
        if (bark >= dogs[i]) {
            dogs[i] = bark   K;
            found = true;
            break;
        }
    }
    if (!found)
    {
        dogs.push_back(bark   K);
    }
}
  

PS не используйте #include <bits/stdc .h> , это нестандартно и работает только на некоторых платформах, вместо этого включите только нужные вам заголовки c (например, <iostream> и <vector> ). using namespace std также может вызвать проблемы.