e-olymp 555. Ближайшие точки

Задача

Антон в школе начал изучать математику. Его внимание привлекло новое для него понятие числовой прямой. Антон быстро научился вычислять расстояния между двумя точками на этой прямой, задавать отрезки и интервалы на ней.

Готовясь к контрольной работе, Антон столкнулся со следующей задачей: На числовой прямой задано $n$ точек. Необходимо найти среди них две ближайшие. Расстояние между двумя точками числовой прямой $x$ и $y$ равно $|x-y|$.

Требуется написать программу, которая поможет Антону решить поставленную задачу.

Входные данные

Первая строка содержит количество точек $n$ $\left(2\leq n \leq 10^{5}\right)$. Вторая строка содержит $n$ различных целых чисел $x_{i}$- координаты заданных точек числовой прямой. Числа в строке разделены пробелом. Значение любой координаты $x_{i}$ не превосходит $10^{9}$
по абсолютной величине.

Выходные данные

В первой строке вывести минимальное расстояние между двумя заданными точками. Во второй строке вывести номера точек, которым соответствует найденное расстояние. Точки нумеруются натуральными числами от $1$ до $n$ в том же порядке, в котором они заданы во входе. Если ответов несколько, выведите любой из них.

Тесты

Входные данные	Выходные данные
5 10 3 6 2 5	1 2 4
6 10 3 6 1 5 11	1 3 5
9 14545690 4343 -6 10 500 1100 -1 2 10	0 4 9
2 1 5	4 2 1
2 -1000000000 1000000000	2000000000 2 1
9 1 5 9 15 3 100 -1 4 10	1 8 5
10 0 1 5 10 20 100 120 250 -100 55	1 2 1

Решение

#include <iostream>
#include <map>
using namespace std;

int main() {
    long long n;
    cin >> n;
    map<long long, long long> Ox;
    long long dis = 0,A = 0,B = 0;//dis- distance
    bool zero_dis = 0;
    for(long long i = 1;i <= n && !zero_dis;i++){
        long long tmp;
        cin >> tmp;
        if(Ox[tmp] != 0){
            zero_dis = true;
            A = Ox[tmp];
            B = i;
            dis = 0;
        }
        else Ox[tmp] = i;
    }
    
    if(!zero_dis){
        dis = -1;
        for(auto i = Ox.begin(),j = ++Ox.begin(); j != Ox.end(); i++, j++){
            long long tmp_dis = j->first - i->first;
            if(dis>tmp_dis || dis<0){
                dis = tmp_dis;
                A = j->second;
                B = i->second;
            }
        }
    }
    cout << dis << "\n" << A << " " << B;
    return 0;
}

#include <iostream>

#include <map>

using namespace std;

int main() {

long long n;

cin >> n;

map<long long, long long> Ox;

long long dis = 0,A = 0,B = 0;//dis- distance

bool zero_dis = 0;

for(long long i = 1;i <= n && !zero_dis;i++){

long long tmp;

cin >> tmp;

if(Ox[tmp] != 0){

zero_dis = true;

A = Ox[tmp];

B = i;

dis = 0;

}

else Ox[tmp] = i;

}

if(!zero_dis){

dis = -1;

for(auto i = Ox.begin(),j = ++Ox.begin(); j != Ox.end(); i++, j++){

long long tmp_dis = j->first - i->first;

if(dis>tmp_dis || dis<0){

dis = tmp_dis;

A = j->second;

B = i->second;

}

cout << dis << "\n" << A << " " << B;

return 0;

}

Объяснение

В начале создаётся ассоциативный контейнер, где каждой точке на прямой ставится в соответствие её номер. Попутно выполняется проверка, не было ли до этого точки с такой же координатой (тогда расстояние между ними равно $0$, соответственно). Затем, поскольку map автоматически выполняет сортировку, сравниваем разность координат рядом стоящих элементов с текущим минимальным расстоянием, и, при необходимости, обновляем значение расстояния и индексы точек, для которых это расстояние верно.

Замечание

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

e-olymp

ideone

Related Images:

Похожее

6 thoughts on “e-olymp 555. Ближайшие точки”

В принципе я с Вами согласен. Только некоторые места вы излишне усложняете. Посмотрите, пожалуйста, такую версию:

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    vector <pair <int, int> > v;
    int a, b, n, x;
    cin >> n;
    v.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> x;
        v[i] = make_pair(x, i + 1);
    }
    sort(v.begin(), v.end());
    int nmin = 1;
    for (int i = 2; i < n; i++)
        if (v[i].first - v[i - 1].first < v[nmin].first - v[nmin - 1].first) 
            nmin = i;
    cout << v[nmin].first - v[nmin - 1].first << "\n" << v[nmin].second << " " << v[nmin - 1].second;
}

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

int main() {

vector <pair <int, int> > v;

int a, b, n, x;

cin >> n;

v.resize(n);

for (int i = 0; i < n; i++) {

cin >> x;

v[i] = make_pair(x, i + 1);

}

sort(v.begin(), v.end());

int nmin = 1;

for (int i = 2; i < n; i++)

if (v[i].first - v[i - 1].first < v[nmin].first - v[nmin - 1].first)

nmin = i;

cout << v[nmin].first - v[nmin - 1].first << "\n" << v[nmin].second << " " << v[nmin - 1].second;

}

Я специально привожу решение с сортировкой, а не с map, чтобы было некоторое разнообразие. Но по сути решение такое-же как Ваше.
Есть только одно замечание — удалите, пожалуйста, пустые строки.

Олег Петров says: 01/04/2019 at 19:18

Поддержу Игоря Евгеньевича, сделав акцент на следующем: сортировка должна работать быстрее, чем map, поскольку она производится на непрерывном участке памяти, а это означает хорошую кэшируемость. При этом map хранит кучу необязательной для нас попутной информации, такой как указатели на левого/правого потомка, и постоянно перебалансируется при добавлениях элементов.

Зато эта структура дает нам возможность поддерживать сортировку «на лету». Если бы задача была сформулирована так, что надо искать пары ближайших точек после каждого добавления новой точки, то использование map было бы оправдано.
Кирилл Веремйов says: 02/04/2019 at 22:52

Я понимаю, что использование map выглядит для данной задачи как пальба из пушки по воробьям, но, на самом деле, выбор данного типа хранения данных для решения этой задачи, обусловлен не столько вопросом оптимизации, как скорее темой, на которую она дана: собственно, map 🙂 Хотя, признаться, я думал, что разница производительности будет менее значительной. Так что, да, перечисленные вами свойства map, в дальнейшем, видимо, лучше не упускать из виду, спасибо
Кирилл Веремйов says: 02/04/2019 at 21:51

Да, спасибо, использование пар тут действительно, пожалуй, будет логичнее и понятнее, чем два параллельно двигающихся итератора. Если вы имели ввиду их, то да, такой вариант получился именно из-за map. Из способов сделать пробег по всем значениям, которые я рассматривал, этот показался самым сбалансированным с точки зрения понятность/эффективность. Хотя, вполне вероятно, есть и более предпочтительный.
По поводу строк… Я проверял, когда публиковал, но во вкладке «Визуально», а нужно было в «Текст». В общем, теперь где нужно поправил, вроде

У написано «Входные» данные вместо «Выходных».

Кирилл Веремйов says: 15/04/2019 at 14:11

Точно, спасибо, исправил

Добавить комментарий Отменить ответ

Для отправки комментария вам необходимо авторизоваться.

C++ для приматов

Начальный курс программирования для студентов направления "Прикладная математика" Одесского национального университета имени И.И.Мечникова

e-olymp 555. Ближайшие точки

Задача

Входные данные

Выходные данные

Тесты

Решение

Объяснение

Related Images:

Понравилось это:

Похожее

6 thoughts on “e-olymp 555. Ближайшие точки”

Добавить комментарий Отменить ответ

Задача

Входные данные

Выходные данные

Тесты

Решение

Объяснение

Related Images:

Поделиться ссылкой:

Понравилось это:

Похожее

6 thoughts on “e-olymp 555. Ближайшие точки”

Добавить комментарий Отменить ответ