Оптимизация кода, не проходит по времени

@Maxim_rus_nev · Регистрация: 01.12.2022

Студворк — интернет-сервис помощи студентам

Вам дан массив a
, содержащий прогноз погоды в Берляндии за последние n
дней. То есть, ai
— это предполагаемая температура воздуха в день i
(1≤i≤n
).

Также вам дан массив b
—температура воздуха, которая была в каждый из дней на самом деле. Однако, все значения в массиве b
перемешались.

Определите, в какой день была какая температура, если известно, что погода никогда не отличается от прогноза более чем на k
градусов. Другими словами, если в день i
настоящая температура воздуха равнялась c
, то всегда верно равенство |ai−c|≤k
.

Например, пусть задан массив a
= [1,3,5,3,9
] длины n=5
и k=2
и массив b
= [2,5,11,2,4
]. Тогда, чтобы значение bi
соответствовало температуре воздуха в день i
, можно переставить элементы массива b
так: [2,2,5,4,11
]. Действительно:

В 1
-й день |a1−b1|=|1−2|=1
, выполняется 1≤2=k
Во 2
-й день |a2−b2|=|3−2|=1
, выполняется 1≤2=k
В 3
-й день |a3−b3|=|5−5|=0
, выполняется 0≤2=k
В 4
-й день |a4−b4|=|3−4|=1
, выполняется 1≤2=k
В 5
-й день |a5−b5|=|9−11|=2
, выполняется 2≤2=k
Входные данные
Первая строка входных данных содержит целое число t
(1≤t≤104
) — количество наборов входных данных в тесте.

Далее следуют описания наборов входных данных.

В первой строке каждого набора входных данных записано два целых числа n
(1≤n≤105
) и k
(0≤k≤109
) — количество дней и максимальная разница между предполагаемой и реальной температурой воздуха в каждый из дней.

Во второй строке каждого набора входных данных записано ровно n
целых чисел — элементы массива a
(−109≤ai≤109
).

Во третьей строке каждого набора входных данных записано ровно n
целых чисел — элементы массива b
(−109≤bi≤109
).

Гарантируется, что сумма n
по всем наборам не превышает 105
, и что элементы массива b
всегда можно переставить таким образом, чтобы равенство |ai−bi|≤k
было верно для всех i
.

Выходные данные
В отдельной строке для каждого набора входных данных выведите ровно n
чисел — значения температуры воздуха в каждый из дней в правильном порядке.

Если существует несколько вариантов ответа — выведите любой из них.
Пример
входные данные
3
5 2
1 3 5 3 9
2 5 11 2 4
6 1
-1 3 -2 0 -5 -1
-4 0 -1 4 0 0
3 3
7 7 7
9 4 8
выходные данные
2 2 5 4 11
0 4 -1 0 -4 0
8 4 9

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>
#include <vector>
#include <string>
#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int t, n, greh;
    int p;
    cin >> t;
    vector<int> a, b,pose;
    for (int i = 0; i < t; ++i)
    {
        cin >> n >> greh;
        for (int g = 0; g < n; g++)
        {
            cin >> p;
            a.push_back(p);
        }
        for (int j = 0; j < n; j++)
        {
            cin >> p;
            b.push_back(p);
        }
        pose = a;
        sort(a.begin(),a.end());
        sort(b.begin(),b.end());
        while ((int)pose.size()>0)
        {
            for(int u = 0; u<(int)a.size();++u)
            {
                if (a[u] == pose[0])
                {
                    cout<<b[u]<<" ";
                    a.erase(a.begin()+u);
                    b.erase(b.begin()+u);
                    pose.erase(pose.begin());
                    break;
                }
            }
        }
cout<<"\n";
 
 
}
}

-----------------------------------------------------------------------------------------------------------------------------------------------------
Код рабочий, но на пятом тесте(неизвестном) валится по времени(ограничение по времени 1 секунда). Подскажите пожалуйста как оптимизировать код

@TheCalligrapher · 11.06.2023, 18:00

Сообщение от Royal_X

(конечно, в нашем случае можно было захватить не все переменные, а только &a)

Ну вообще-то неправильно говорить, что такая лямбда "захватывает все переменные". [&] - это указание, что неявный (то есть "автоматический") захват следует делать по ссылке. Такой захват будет захватывать не все переменные, а только те, которые нужны лямбде. В данном случае будет захвачено только a.

@Royal_X · 11.06.2023, 18:21

Сообщение от TheCalligrapher

Ну вообще-то неправильно говорить, что такая лямбда "захватывает все переменные".

Ну понятно же, что в моем объяснении под "все" не подразумевались прям все все все... Если придираться ко словам, то ваш ответ тоже не вишня. Вот, что за термин

Сообщение от TheCalligrapher

которые нужны лямбде

?
Если ТС хочет вдаваться в детали, то может прочесть https://en.cppreference.com/w/cpp/language/lambda
Я лишь писал в общих чертах.

@TheCalligrapher · 12.06.2023, 20:47

Сообщение от TheCalligrapher

// Строим сортирующую from-перестановку для массива `a`

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

В примере ниже требуемый адаптор ItDeref реализован мною вручную. Вполне возможно, что такая функциональность уже есть в Boost или в стандартных диапазонах

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <vector>
#include <algorithm>
#include <iostream>
#include <iterator>
 
template <typename IT> class ItDeref
{
public:
  using iterator_category = typename std::iterator_traits<IT>::iterator_category;
  using difference_type = typename std::iterator_traits<IT>::difference_type;
  using value_type = std::remove_reference_t<decltype(**std::declval<IT>())>;
  using pointer = value_type *;
  using reference = value_type &;
 
  ItDeref() {}
  ItDeref(const IT &it) : it(it) {}
 
  reference operator *() const 
    { return **it; }                                                     
  pointer operator ->() const 
    { return *it; }
    
  ItDeref &operator ++()
    { ++it; return *this; }
 
  ItDeref operator ++(int)
    { ItDeref old = *this; ++it; return old; }
 
  ItDeref &operator --()
    { --it; return *this; }
 
  ItDeref operator --(int)
    { ItDeref old = *this; --it; return old; }
 
  ItDeref &operator +=(difference_type rhs)
    { it += rhs; return *this; }
 
  ItDeref &operator -=(difference_type rhs)
    { it -= rhs; return *this; }
 
  friend difference_type operator -(const ItDeref &lhs, const ItDeref &rhs)
    { return lhs.it - rhs.it; }
  friend ItDeref operator +(const ItDeref &lhs, difference_type rhs)
    { return ItDeref(lhs) += rhs;  }
  friend ItDeref operator -(const ItDeref &lhs, difference_type rhs)
    { return ItDeref(lhs) -= rhs;  }
 
  friend auto operator <=>(const ItDeref &, const ItDeref &) = default;
  friend bool operator ==(const ItDeref &, const ItDeref &) = default;
 
protected:
  IT it;
};
 
int main()
{
  unsigned t = 0;
  std::cin >> t;
  for (; t > 0; --t)
  {
    // Читаем входные данные
    unsigned n = 0, k = 0;
    std::cin >> n >> k;
    
    // Читаем входные данные - пока только массив `a`
    std::vector<int> a(n);
    std::copy_n(std::istream_iterator<int>(std::cin), n, a.begin());
    
    // Строим индекcный массив для массива `a` из указателей
    std::vector<int *> ptrs;
    ptrs.reserve(n);
    for (int &ra : a)
      ptrs.push_back(&ra);
      
    // Сортируем индекcный массив по значениям из `a`
    std::sort(ptrs.begin(), ptrs.end(), [&](const int *lhs, const int *rhs) { return *lhs < *rhs; });
    
    // Читаем данные массива `b` в массив `a`
    std::copy_n(std::istream_iterator<int>(std::cin), n, a.begin());
    
    // Сортируем массив `a`, смотря на него сквозь массив `ptrs`    
    std::sort(ItDeref(ptrs.begin()), ItDeref(ptrs.end()));
    
    // Выводим `a` в полученном порядке
    for (int v : a)
      std::cout << v << " ";
    std::cout << std::endl;  
  }
}

Алексей1153 · 12.06.2023, 22:54

мой вариант

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
#include <vector>
#include <algorithm>
 
struct s_item
{
    int prognosis{};
    int reality{};
    size_t pos{};
};
 
int main()
{
    int tasks; std::cin >> tasks;
    
    std::vector<s_item> list;
    std::vector<int> reality;
    for (int task=0; task!= tasks; task++)
    {
        int days,diff; std::cin>>days>>diff;
        
        list.resize(days);
        reality.resize(days);
 
        size_t pos=0;
        for(auto& item:list){std::cin>>item.prognosis; item.pos=pos++;}
        
        for(auto& к:reality){std::cin>>к;}
        
        std::sort(list.begin(), list.end(), [](const auto& l, const auto& r)noexcept
        {return l.prognosis<r.prognosis;});
 
        std::sort(reality.begin(), reality.end());
 
        auto it_r=reality.begin();
        for(auto& item:list){item.reality=*it_r; it_r++;};
        
        std::sort(list.begin(), list.end(), [](const auto& l, const auto& r)noexcept
        {return l.pos<r.pos;});
        
        for(const auto& item:list){std::cout<<item.reality<<' ';}
        
        std::cout<<'\n';
    }
}

Новые блоги и статьи Все статьи Все блоги /
Алиса нашла кучу ошибок компиляции и запуска в проекте, который без проблем компилировался и запускался))) anaschu 30.06.2026 Я пока посмеюся, но завтра проверю. А вообще интерсно. Дал алисе файл, в котором точно нет ошибок компиляции и запуска, и попросил их найти. Нашла кучу))) Критические ошибки, мешающие компиляции и. . .	сукцессия 16. Общий обзор, в основном что бы другие ии поняли anaschu 29.06.2026 # Передаточный документ: модель микоризной сукцессии (для нового чата) Этот документ предназначен для того, чтобы новый чат Claude мог продолжить работу без необходимости заново разбираться в. . .	сукцессия 15 неявная схема anaschu 29.06.2026 Алиса Калибровка параметров симбиотической модели: технический обзор Содержание: Введение Постановка проблемы Технические аспекты реализации Процесс внедрения изменений	сукцессия 14. Обновленная схема модели anaschu 28.06.2026 ГЛОБАЛЬНАЯ ОПИСАТЕЛЬНАЯ СПЕЦИФИКАЦИЯ ЭКОСИСТЕМНОЙ МОДЕЛИ «SOIL CHEMISTRY & MYCORRHIZA 2. 0» https:/ / ibb. co/ NnkGpfMd Представленная интегрированная схема описывает непрерывную нелинейную. . .
сукцессия 13. Питон модель трехзонного мицелия, пока что в основном арбускулярного anaschu 28.06.2026 ## Разработка агентной модели микоризной сукцессии: от выявления артефактов к созданию комплексной системы ### Аннотация Представлено исследование по разработке агентной модели микоризной. . .	сукцессия 12. краткий список проверок модели перед запуском. anaschu 27.06.2026 Скрытые отказы в моделях систем динамики (SD-models) экологических систем: два случая из практики Контекст Разбирался прототип модели систем динамики (SD-модели) микоризной сукцессии: пять. . .	Сукцессия 11. Проверка орудий перед войной: разработка через тестирование anaschu 27.06.2026 Как не дать модели соврать самой себе: проверки для симуляции микоризной сукцессии Введение Когда вы строите математическую модель живой системы — грибов, растений, почвы — главная опасность. . .	10 сукцессия. Питон код войны грибов и растений anaschu 27.06.2026 import numpy as np class PlantAgent: def __init__(self, name, strategy, initial_biomass): self. name = name self. strategy = strategy # "greedy" (широколиственные) или. . .