Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Пересечение множеств

(Время: 1 сек. Память: 64 Мб Сложность: 34%)

Эта задача сложна своими ограничениями. Самое ресурсоемкое, но простое решение, которое может прийти в голову - это считать данные в массивы, исключить из них повторяющиеся элементы, далее пробегая по одному из них смотреть: есть ли он во втором и если есть, то выводить в выходной файл. Здесь только исключение повторящихся элементов может при неэффективном решении иметь сложность O(n2), что для миллиона элементов может вызвать TLE (Time limit exceeded).

Рассмотрим теперь верное решение этой задачи. Здесь вовсе не нужны два массива, длина которых может быть до миллиона. В силу конечности диапазона возможных значений мы можем описать некоторый массив a[i] для i=0..105, в i-м значении будем хранить 0, если число i не содержится ни в одном из двух наборов чисел. Если число i имеется в первом наборе, то запишем туда 1, а если и в обоих наборах, то запишем туда 2. После чего пробегая по массиву нужно будет вывести все i, у которых a[i]=2. Заполнение массива a[i] происходит следующим образом: сначала все элементы обнуляются, далее при чтении элемента x первого набора можно выполнять присваивание a[x]=1. При просмотре элементов второго набора для каждого элемента y можно a[y]=2 только в том случае, когда a[y]=1.

Приведенный выше алгоритм можно формализовать к следующему виду:

int a[0..105]={0...0};

read(n,m);
for i=1..n{
  read(x);
  a[x]=1;
}
for i=1..m{
  read(y);
  if(a[y]==1) a[y]=2;
}
for i=0..105{
  if(a[i]==2) write(i,' ');
}

[Обсуждение] [Все попытки] [Задача]


Красноярский краевой Дворец пионеров, (c)2006 - 2020, E-mail: admin@acmp.ru