set - множество - хранит упорядоченные по возрастанию элементы в виде дерева каждый ровно один раз
multiset - мультимножество - хранит упорядоченные по неубыванию элементы в виде дерева
каждый элемент может встречаться несколько раз
Объявление
set<string> s; // множество строк, строки упорядочены по возрастанию
// добавление одинаковых игнорируется
// каждое строка может встречаться один раз
multiset<int, greater<int> > s; // множество чисел, числа упорядочены по убыванию
// одинаковые числа добавляются
// каждое число может встречаться несколько раз
Использование
s.insert(t) // вставить элемент t в множество s
s.find(t) // найти t в s
проверить, есть ли элемент t во множестве s
нет, если s.find(t)==s.end()
есть, если s.find(t)!=s.end()
s.end - адрес "сразу за последним элементом "
s.erase(s.find(h)) // найти в s элемент h и удалить его
s.erase(h) // в multiset удаляет все элементы со значением h
s.clear() // удалить все элементы из s
s.empty() // множество пустое?
s.size() // количество элементов в s
*s.begin() // взять первый - наименьший элемент из s (если элементы хранятся по возрастанию)
// - наибольший элемент из s (если элементы хранятся по убыванию)
*s.rbegin() // взять последний
*--s.end() // взять последний - наибольший элемент из s (если элементы хранятся по возрастанию)
// - наименьший элемент из s (если элементы хранятся по убыванию)
// s.end - адрес "сразу за последним элементом"
Заметим, что первый, последний элементы и empty берутся за O(1),
а insert, find, erase выполняются за O(LogN)
set <pair< pair<int,int> , pair<int,int> > > s; set <pair< pair<int,int> , pair<int,int> > >::iterator is; for (is=s.begin(); is!=s.end(); is++)
for (is=s.begin(); is!=s.end(); is++)
{
int x1,y1,x2,y2;
x1=is->first.first; y1=is->first.second; x2=is->second.first;
y2=is->second.second;
Задача из курса "Методы алгоритмизации"
Олимпиады по информатике\Стек\07_Rub6 - "aPhone
http://dl.gsu.by/task.jsp?nid=256579&cid=15
Решение
Можно симулировать процесс, описанный в условии задачи.
А можно заметить, что если сначала все строки прочитать,
а потом обрабатывать их с конца, то задача может существенно упроститься
Список строк пустой
Пока не обработали все строки
- если текущей строки нет,
Тогда выводим её, и заносим её в список
иначе пропускаем
Довыводим <Empty> если нужно
Для того, чтобы не писать самим процедуры
добавления строки в список проверки и проверки наличия строки в списке
(а также для ускорения этих процедур) можно
определить тип множество строк (set<string> s)
и использовать стандартные функции.
s.insert(t) - вставить строку t в множество s
s.find(t) - проверить, есть ли строка t во множестве s
есть, если s.find(t)==s.end()
#include <bits/stdc++.h>
using namespace std;
string x[1000];
set<string> s;
int main()
{
freopen("aphone.in","r",stdin);
freopen("aphone.out","w",stdout);
int n,m,i;
cin >> m >> n;
for (i=0; i<n; i++) cin >> x[i];
for (i=n-1; (i>=0) && (m>0); i--)
if (s.find(x[i])==s.end())
{ s.insert(x[i]); cout << x[i] << endl; m--;};
for (i=0; i<m; i++) cout << "<Empty>" << endl;
}
Подробнее о set
http://informatics.mccme.ru/mod/book/view.php?id=492&chapterid=215