A21093.营业额统计 全站最速题解

#include <iostream>
#include <set>
#include <algorithm>
#include <iterator>
#include <limits>

void solve() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    std::cin >> n;

    if (n == 0) {
        std::cout << 0 << '\n';
        return;
    }

    long long total_fluctuation = 0;
    std::set<int> previous_turnovers;

    int first_turnover;
    std::cin >> first_turnover;
    total_fluctuation = first_turnover;
    previous_turnovers.insert(first_turnover);

    for (int i = 1; i < n; ++i) {
        int current_turnover;
        std::cin >> current_turnover;

        long long min_fluctuation_for_day = std::numeric_limits<long long>::max();

        auto it_geq = previous_turnovers.lower_bound(current_turnover);

        if (it_geq != previous_turnovers.end()) {
            min_fluctuation_for_day = std::min(min_fluctuation_for_day, (long long)*it_geq - current_turnover);
        }

        if (it_geq != previous_turnovers.begin()) {
            auto it_less = std::prev(it_geq);
            min_fluctuation_for_day = std::min(min_fluctuation_for_day, (long long)current_turnover - *it_less);
        }
        
        if (min_fluctuation_for_day == std::numeric_limits<long long>::max()){
            min_fluctuation_for_day = 0;
        }

        total_fluctuation += min_fluctuation_for_day;
        previous_turnovers.insert(current_turnover);
    }
    
    std::cout << total_fluctuation << '\n';
}

int main() {
    solve();
    return 0;
}