Форум Всеукраїнської інтернет-олімпіади NetOI

#include <bits/stdc++.h>


using namespace std;

#define INF 1e18//10^18

long long max(long long x, long long y){
    return ((x>y)?x:y);
}

long long min(long long x, long long y){
    return ((x<y)?x:y);
}

int main()
{
    int n;
    long long minDiff=INF;
    scanf("%d", &n);
    vector<int> a(n);
    for(int i=0; i<n; i++)
        scanf("%d", &a[i]);
    for(int i=1; i<n; i++)
        minDiff=min(minDiff, ( max(a[i], a[i-1])-min(a[i], a[i-1]) ));
    printf("%d", minDiff);
    return 0;
}

/*
Итак. Идея решения.
Ну для n=2 всё понятно: max(a[0], a[1])-min(a[0], a[1]) - это и будет ответ.
Тогда без ограничения общности экстраполируем частный случай на общий(красиво, правда?)) ): пусть возьмем первые два элемента массива а.
Добавим третий к рассмотрению. Он мог:
-оказаться больше max(a[0], a[1]), тогда он станет максимальным(минимальный не изменится) и тогда его брать не выгодно(ответ станет больше, а нам надо минимальную разность).
-оказаться посередине между max и min. Ну как бы всё равно: ответ не изменился.
- оказаться меньше min(как первый случай, только наоборот).
Вывод: делать отрезки больше, чем в 2 эл-та не выгодно. Рассматриваем только отрезки длины 2. А их мы считать умеем.
ТЫДЫЩЬ - AC!
*/

Відредаговано GeniusDP (2020-11-11 15:50:27)