Решение задачи №1222 «Телефонный справочник» с ACMP
Условие задачи
У Вас в наличии есть телефонный справочник с информацией о номерах телефонов и адресов абонентов.
Требуется реализовать эффективную структуру данных, реализующую поиск информации об абонентах по номерам телефонов.
Входные данные
Первая строка входного файла INPUT.TXT содержит два натуральных числа N и M (N,M ≤ 30 000) – количество абонентов и количество запросов по номеру телефона соответственно.
Далее в 3∙N строках следует содержание телефонного справочника, где информация о каждом из абонентов занимает 3 строки и имеет вид:
<номер телефона>
<фамилия> <имя> <отчество>
<улица> <дом>-<квартира>
Где «номер телефона» – целое число, состоящее из 6 цифр. Здесь «дом» и «квартира» – натуральные числа, не превосходящие 100. Все строки во входных данных состоят не более, чем из 50 символов.
Далее следует M строк с информацией о номерах телефонов абонентов, информацию о которых необходимо получить. Гарантируется, что все номера телефонов присутствуют в телефонном справочнике.
Выходные данные
В выходной файл OUTPUT.TXT для каждого номера телефона в запросе выведите информацию об абоненте в следующем формате:
<фамилия> <имя> <отчество> (<улица> <дом>-<квартира>)
Решение на C++
#include<iostream>
#include<string>
using namespace std;
struct abon{ int nom; string fio; string adr;
};
void Quick(abon a[],int n){
if(n<2)return;
int L=0,R=n-1,m=a[n/2].nom;
do{while(a[L].nom<m)L++; while(a[R].nom>m)R--;
if(L<=R){swap(a[L],a[R]);L++;R--;}
}while(L<=R);
Quick(a,R+1); Quick(a+L,n-L);
}
main(){
abon a[30000]; int n,m,i,k,j,L,R;string c;
cin>>n>>m;
for (i=0;i<n;++i){
cin>>a[i].nom;
getline(cin,c);
getline(cin,a[i].fio);
getline(cin,a[i].adr);
}
Quick(a,n);
for(j=0;j<m;++j){
cin>>k;
L=0; R=n;
do{ i=(L+R)/2;
if(a[i].nom>k)R=i; else L=i;
}while(a[i].nom!=k);
cout<<a[i].fio<<" ("<<a[i].adr<<')'<<endl;
}
}
Условия задач взяты с сайта acmp.ru