Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.67/3: Рейтинг темы: голосов - 3, средняя оценка - 4.67
0 / 0 / 0
Регистрация: 24.09.2023
Сообщений: 3

Найти пары одинаковых значений из двух последовательностей

24.09.2023, 16:59. Показов 709. Ответов 11
Метки с++ (Все метки)

Студворк — интернет-сервис помощи студентам
Всем привет, помогите оптимизировать код задачи.

Задача:
У Никиты и Дианы день рождения в один день!

Никите Ярик подарил последовательность целых чисел a1,a2,…,an - размера n
, а Диане последовательность b1,b2,…,bm - размера m.

Вообще, Никита и Диана во многом похожи – день рождения в один день, оба учатся в Петрозаводском Государственном Университете, оба участники Клуба Творчества Программистов. В связи с такими интересными фактами, они решили проверить вообще все в жизни пункты, по которым они между собой могут оказаться похожими.

Начать они решили с подсчета похожести последовательностей, которые у них есть. Похожестью двух последовательностей назовем число пар чисел (i,j) таких, что (1≤i≤n), (1≤j≤m) и ai=bj.

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

Входные данные:
В первой строке вам задано число n (1≤n≤2⋅105) — размер Никитиной последовательности.

Во второй строке задана последовательность Никиты — a1,a2,…,an (1≤ai≤109).

В третьей строке вам задано число m (1≤m≤2⋅105) — размер Дианиной последовательности.

Во четвертой строке задана последовательность Дианы — b1,b2,…,bm (1≤bj≤109).

Выходные данные:
Выведите одно число — похожесть последовательности Дианы и Никиты.

Пример:
Входные данные:
6
1 2 3 4 5 6
4
4 5 6 7
Выходные данные:
3

Входные данные:
10
1 1 1 1 1 2 2 2 2 2
10
2 2 2 2 2 1 1 1 1 1
Выходные данные:
50

Я написал код, и не могу понять, как его можно ещё ускорить:

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
90
91
92
93
94
95
96
97
98
99
#include "iostream"
#include <vector>
#include <algorithm>
 
using namespace std; 
 
int main () {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
 
  long long sc = 0;
  int n; vector <int> vec_a;
  int m; vector <int> vec_b;
  cin >> n;
  for (int i = 0; i < n; i++) {
    int a;
    cin >> a;
    vec_a.push_back(a);
  }
  cin >> m;
  for (int i = 0; i < m; i++) {
    int b;
    cin >> b;
    vec_b.push_back(b);
  }
  
  sort (vec_a.begin(), vec_a.end());
  sort (vec_b.begin(), vec_b.end());
 
  if(n >= m){
    int prev_j = 0;
    int sc_prev = 0; 
    int sc_pred = 0;
    int num_pred = vec_b[0];
    for(int i = 0; i < m; i++){                         
        if((i>0)&&(vec_b[i] > vec_b[i-1])){
            for(int j = prev_j; j < n; j++){
                if(vec_b[i] == vec_a[j]) sc++;
                else if(vec_b[i] < vec_a[j]) { 
                    prev_j = j;
                    break;
                }
            }
            sc_pred = sc - sc_prev;
        }
        else if(i == 0){
            for(int j = prev_j; j < n; j++){
                if(vec_b[i] == vec_a[j]) sc++;
                else if(vec_b[i] < vec_a[j]) { 
                    prev_j = j;
                    break;
                }
            }
            sc_pred = sc - sc_prev;
        }
        else{
            sc+=sc_pred;   
        }
        sc_prev = sc;
    }
  }
  
  
  else{
    int prev_j = 0;
    int sc_prev = 0; 
    int sc_pred = 0;
    int num_pred = vec_a[0];
    for(int i = 0; i < n; i++){                         
        if((i>0)&&(vec_a[i] > vec_a[i-1])){
            for(int j = prev_j; j < m; j++){
                if(vec_a[i] == vec_b[j]) sc++;
                else if(vec_a[i] < vec_b[j]){ 
                    prev_j = j;
                    break;
                }
            }
            sc_pred = sc - sc_prev;
        }
        else if(i == 0){
            for(int j = prev_j; j < n; j++){
                if(vec_a[i] == vec_b[j]) sc++;
                else if(vec_a[i] < vec_b[j]) { 
                    prev_j = j;
                    break;
                }
            }
            sc_pred = sc - sc_prev;
        }
        else{
            sc+=sc_pred;   
        }
        sc_prev = sc;
    }
  }
 cout << sc;
  return 0;
}
0
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
24.09.2023, 16:59
Ответы с готовыми решениями:

Найти все пары одинаковых значений
Найти все пары одинаковых значений среди четырёх переменных. переменные вводятся любые с клавиатуры. помогите пожалуйста

Найти все пары одинаковых значений среди 4х переменных
1. Найти все пары одинаковых значений среди 4х переменных.

Объединение двух последовательностей, сохраняя исходный порядок первой, при одинаковых элементах сортировка по второй
Даны две последовательности положительных целых чисел A и B, которые объединили по следующему признаку: первая цифра первого элемента пары...

11
 Аватар для igorrr37
2869 / 2016 / 991
Регистрация: 21.12.2010
Сообщений: 3,720
Записей в блоге: 15
24.09.2023, 17:19
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
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <cstdint>
 
using ui = uint64_t;
 
int main()
{
    std::vector<int> va{ 1,2,3,4,5,6 }, vb{ 4,5,6,7 };
    std::unordered_map<int, ui> umpa, umpb;
    for (auto val : va)
    {
        umpa[val]++;
    }
    for (auto val : vb)
    {
        umpb[val]++;
    }
    ui res{};
    for (auto const& [k, v] : umpa)
    {
        if (auto it = umpb.find(k); it != umpb.end())
        {
            res += v * it->second;
        }
    }
    std::cout << res;
}
0
Заблокирован
24.09.2023, 17:27
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
#include <iostream>
#include <map>
 
int main()
{
   using std::cin; using std::cout; using std::endl;
   int n, m;
   std::map<int, int> Diana, Nikita;
   
   cin >> n;
   while(n--){
      int elem;
      cin >> elem; 
      ++Diana[elem];
   }
   cin >> m;
   while(m--){
      int elem;
      cin >> elem; 
      ++Nikita[elem];
   }
   int res = 0;
   for(const auto& v: Diana)
      res += v.second * Nikita[v.first];
   cout << res << endl;
}
Добавлено через 1 минуту
Цитата Сообщение от igorrr37 Посмотреть сообщение
std::unordered_map
Да, для данной задачи сортировать не нужно.
0
Модератор
Эксперт С++
 Аватар для zss
13766 / 10960 / 6490
Регистрация: 18.12.2011
Сообщений: 29,234
24.09.2023, 17:29
А вот так попробуйте:
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
#include <iostream>
#include <set>
using namespace std; 
int main () {
    set<int> vec_a;
    set<int> vec_b;
    size_t n; 
    cout << "n=";
    cin >> n;
    for (size_t i = 0; i < n; i++)
    {
        cout <<"a["<<i<<"]=";
        int a;cin>>a;
        vec_a.insert(a);
    }
    size_t m;
    cout<<"m=";
    cin >>m;
    for (size_t i = 0; i < m; i++)
    {
        cout <<"b["<<i<<"]=";
        int b;cin>>b;
        vec_b.insert(a);
    }
    cin.get();
    int sc=0;
    set<int>::iterator p;
    for( p = vec_a.begin(); p != vec_a.end();++p)
    { 
        if(vec_b.find(*p)!=vec_b.end())
            ++sc;
    }
    cout <<"Total equal pairs:"<< sc<<endl;
    cin.get();
    return 0;
}
0
0 / 0 / 0
Регистрация: 24.09.2023
Сообщений: 3
24.09.2023, 18:24  [ТС]
Ваше решение не работает на 2-м примере

Цитата Сообщение от igorrr37 Посмотреть сообщение
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
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <cstdint>
using ui = uint64_t;
int main()
{
    std::vector<int> va{ 1,2,3,4,5,6 }, vb{ 4,5,6,7 };
    std::unordered_map<int, ui> umpa, umpb;
    for (auto val : va)
    {
        umpa[val]++;
    }
    for (auto val : vb)
    {
        umpb[val]++;
    }
    ui res{};
    for (auto const& [k, v] : umpa)
    {
        if (auto it = umpb.find(k); it != umpb.end())
        {
            res += v * it->second;
        }
    }
    std::cout << res;
}
Добавлено через 1 минуту
На тесте 53 задачи, она валит из-за неверного ответа, в моем случае это было из-за того, что я использовал int, вместо long, я попробовал сделать на вашем решении тоже самое, но не помогло

Цитата Сообщение от SmallEvil Посмотреть сообщение
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
#include <iostream>
#include <map>
int main()
{
   using std::cin; using std::cout; using std::endl;
   int n, m;
   std::map<int, int> Diana, Nikita;
cin >> n;
   while(n--){
      int elem;
      cin >> elem; 
      ++Diana[elem];
   }
   cin >> m;
   while(m--){
      int elem;
      cin >> elem; 
      ++Nikita[elem];
   }
   int res = 0;
   for(const auto& v: Diana)
      res += v.second * Nikita[v.first];
   cout << res << endl;
}
Добавлено через 1 минуту
Ваше решение также неправильно работает со вторым примером

Цитата Сообщение от zss Посмотреть сообщение
А вот так попробуйте:
0
677 / 479 / 216
Регистрация: 06.09.2013
Сообщений: 1,312
24.09.2023, 19:49
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <map>
 
int main() {
    std::map<int, std::array<size_t, 2>> map{};
    auto enterSeq = [&map](size_t i){
        size_t n;
        std::cin >> n;
        for(;n != 0; n--) {
            int e;
            std::cin >> e;
            map[e][i]++;
        }
    };
    enterSeq(0);
    enterSeq(1);
    size_t result = 0;
    for(const auto& [k, c]: map) {
        result += c[0] * c[1];
    }
    std::cout << result << std::endl;
    return 0;
}
0
Заблокирован
24.09.2023, 19:52
Цитата Сообщение от DenTC Посмотреть сообщение
На тесте 53 задачи, она валит из-за неверного ответа
Оно валится потому что у кого то руки кривые, заточены только под копипаст.
0
фрилансер
 Аватар для Алексей1153
6440 / 5634 / 1127
Регистрация: 11.10.2019
Сообщений: 14,980
24.09.2023, 19:55
Цитата Сообщение от DenTC Посмотреть сообщение
Входные данные:
10
1 1 1 1 1 2 2 2 2 2
10
2 2 2 2 2 1 1 1 1 1
Выходные данные:
50
50 ?
0
Заблокирован
24.09.2023, 19:59
Просто переполнение результата, вот и все.
C++
1
size_t res = 0;
Добавлено через 2 минуты
Цитата Сообщение от Алексей1153 Посмотреть сообщение
50 ?
Алексей,
первый элемент (1) Дианы похож на 6-ой элемент Никиты,
первый элемент (1) Дианы похож на 7-ой элемент Никиты,
...
шестой элемент (2) Дианы похож на 1-ый элемент Никиты,
шестой элемент (2) Дианы похож на 2-ой элемент Никиты,
...

Каждый с каждым
0
фрилансер
 Аватар для Алексей1153
6440 / 5634 / 1127
Регистрация: 11.10.2019
Сообщений: 14,980
24.09.2023, 20:04
SmallEvil, хм, а я почему-то понял так, что нужно найти последовательность максимальной длины на обоих наборах
0
0 / 0 / 0
Регистрация: 24.09.2023
Сообщений: 3
24.09.2023, 20:11  [ТС]
Цитата Сообщение от SmallEvil Посмотреть сообщение
Оно валится потому что у кого то руки кривые, заточены только под копипаст.
Дочитайте сообщение до конца, я уже пробовал исправить на long long
0
Заблокирован
24.09.2023, 20:33
Цитата Сообщение от DenTC Посмотреть сообщение
Дочитайте сообщение до конца, я уже пробовал исправить на long long
Что вы там где исправляли мне не видно, да и фиолетово.
Удачи.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
24.09.2023, 20:33
Помогаю со студенческими работами здесь

Написать приложение для поиска одинаковых значений пары ключ-значения в разных словарях
Написать приложение для поиска одинаковых значений пары ключ-значения в разных словарях

Найти пары одинаковых элементов массива
Задан двумерный целочисленный массив. Известно, что среди его элементов есть пары одинаковых элементов. Найти эти пары, напечатать их...

Выяснить, имеются ли пары соседствующих одинаковых символов и оставить только по одному из пары
Прошу помощи с лабораторными работами. а) Выяснить, имеются ли пары соседствующих одинаковых символов и оставить только по одному...

Нужно найти в массиве и распечатать пары одинаковых чисел
Нужно найти в массиве и распечатать пары одинаковых чисел при помощи одномерных массивов. Пример работы программы: Ввод чисел 1 2...

Выбор двух одинаковых значений
В цикле нахожу хэш некоторого количества строк,вывожу в консоль, как теперь сравнить полученные хэши и показать одинаковые?


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
12
Ответ Создать тему
Новые блоги и статьи
Новый ноутбук
volvo 07.12.2025
Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов
Argus19 22.11.2025
Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Programma_Boinc 20.11.2025
Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .
Ломающие изменения в C#.NStar Alpha
Etyuhibosecyu 20.11.2025
Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .
Мысли в слух
kumehtar 18.11.2025
Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .
Создание Single Page Application на фреймах
krapotkin 16.11.2025
Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .
Фото: Daniel Greenwood
kumehtar 13.11.2025
Расскажи мне о Мире, бродяга
kumehtar 12.11.2025
— Расскажи мне о Мире, бродяга, Ты же видел моря и метели. Как сменялись короны и стяги, Как эпохи стрелою летели. - Этот мир — это крылья и горы, Снег и пламя, любовь и тревоги, И бескрайние. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru